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

        Node currentNode;

        while (!nodes.isEmpty()) {
                currentNode = nodes.pop();
                Node right = currentNode.right();
                if (right != null) {
                Node left = currentNode.left();
                if (left != null) {
                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)?

4 Years
Discussion Span
Last Post by 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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.