Time Complexity for Constructing Binary Tree

[DanHu]

Hi, I am trying to create a binary tree from a string read from a file. The string contains information that tells which is the new left and right nodes, and the node which new these nodes are to be added (assuming there is a root node in the tree already). To find the node of where the 2 new nodes should be added, I used preorder tree traversal:

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);
        }
}

This is from Wikipedia's Tree Traversal page but mine is does the same thing except it returns the node rather than print it. The complexity of preorder traversal is O(n). So my question is, if there are n nodes in the file to add to the tree, and for each node I have to call the above code, does that mean the contruction of the whole tree will be O(n^2)?

[ztini]

Yes, this is O(n^2). You basically have 2 loops: an outer loop of nodes to add to the tree and an inner loop of nodes already in the tree. The outer shrinks while the inner grows, but overall you will average O(n^2) for really large number of nodes.