CODEWITHSUNDEEP
javatreetime-complexity
Dan
Dan

Reputation: 8533

Time Complexity of InOrder Tree Traversal of Binary Tree O(n)?

public void iterativePreorder(Node root) {
        Stack nodes = new Stack();
        nodes.push(root);

        Node currentNode;

        while (!nodes.isEmpty()) {
                currentNode = nodes.pop();
                Node right = currentNode.right();
                if (right != null) {
                        nodes.push(right);
                }
                Node left = currentNode.left();
                if (left != null) {
                        nodes.push(left);      
                }
                System.out.println("Node data: "+currentNode.data);
        }
}

Source: Wiki Tree Traversal

Is the time complexity going to be O(n)? And is the time complexity going to be the same if it was done using recursion?

New Question: If I were to use to above code to find a certain node from a TreeA to create another tree TreeB which will have as much nodes as TreeA, then would the complexity of creating TreeB be O(n^2) since it is n nodes and each node would use the above code which is O(n)?

Upvotes: 5

Views: 18953

Answers (1)

thkala
thkala

Reputation: 86443

Since the traversal of a binary tree (as opposed to the search and most other tree operations) requires that all tree nodes are processed, the minimum complexity of any traversal algorithm is O(n), i.e. linear w.r.t. the number of nodes in the tree. That is an immutable fact that is not going to change in the general case unless someone builds a quantum computer or something...

As for recursion, the only difference is that recursive method calls build the stack implicitly by pushing call frames to the JVM stack, while your sample code builds a stack explicitly. I'd rather not speculate on any performance difference among the two - you should profile and benchmark both alternatives for each specific use case scenario.

Upvotes: 18

Related Questions