1,105,169 Community Members

Time Complexity for Constructing Binary Tree

Member Avatar
DanHu
Newbie Poster
4 posts since Sep 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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

Member Avatar
ztini
Posting Whiz in Training
291 posts since Jan 2011
Reputation Points: 8 [?]
Q&As Helped to Solve: 52 [?]
Skill Endorsements: 0 [?]
 
0
 

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.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: