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

Question

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)?

yes, because you're hitting the N elements in the tree one time. — Luiggi Mendoza
1. Post new questions separately please. 2. I do not understand how exactly TreeB is supposed to be created... — thkala

thkala thkala · Accepted Answer · 2012-03-11T20:48:14

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.

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

1 Answers