Make delicious recipes!

Construct binary search tree from PreOrder traversal


Given a preorder traversal, there can be lots of binary trees.
But if try to keep the tree nearly balanced, then there is only one solution for a given traversal.

O(n2) solution:
First number in the preorder has to be the root of the BST always.
So that becomes the root of the solution tree.
Next, preorder traversal prints the left subtree first and then the right subtree.
Right subtree has greater elements than root and left subtree has smaller.
So, if we find the index 'k' of first element greater than the root, then left subtree could be formed from elements 0 to 'k-1' and right subtree can be formed from elements 'k' to end.
Finding the 'k' at every substep needs O(n) time, so total order of the solution is O(n2)

O(n) solution:
If we use the trick from BST test, then there is no need to find the element 'k'
Every next data in the input is checked to see if it lies within the range of parent-node.
If the data falls within the range, then it forms the left/right child of current node, else it is compared with parent of parent.


// Should be called as createTree (pre, -1, -1, pre.length)

int pos=0;
TreeNode createTree( int pre[], int min, int max, int size )
{
    if( pos >= size )
        return null;
  
    TreeNode root = null;
    int currData = pre[pos];

    boolean inLeftRange  = (min == -1 || currData > min);
    boolean inRightRange = (max == -1 || currData < max);

    if (inLeftRange && inRightRange)
    {
        root = new TreeNode ( currData );
        pos++;
         
        // since pos is global, each call to left subtree changes its value and 
        // the same is reflected before call to right subtree is made.
        root.left  = createTree( pre, min, currData, size );
        root.right = createTree( pre, currData, max, size );
    }

    return root;
}


Example Run:

Let given pre[] = [9, 5, 3, 4, 7, 12, 11, 14]
Below figures show the formation of tree using the O(n) algorithm.

1) 
   9

2) 
   9
  /
 5


3) 
    9
   /
  5
 /
3

4) 4 does not fall in the range -1 to 3, so null is returned from left recursion here. 
Tree remains unchanged and we try the right subtree of 3

5) Range check passes here because 4 lies between (3, 5)
    9
   /
  5
 / 
3
 \
  4


6) As in step 4, the next number 7 does not fall in left range (3,4), so tree remains unchanged and we try right subtree of 4. 
    9
   /
  5
 /
3
 \
  4

7) 7 does not fall even in the right range of 4 which is (4, 5), so we return from this point and go back to node 5.
    9
   /
  5
 /
3
 \
  4

8) Here 7 falls in range (5, 9), so it becomes right child of 5
    9
   /
  5
 / \
3   7
 \
  4

9) Similarly, 12 becomes right child of 9
    9
   / \
  5   12
 / \
3   7
 \
  4

10) Finally, the tree becomes the following
      9
    /  \
   /    \
  5      12
 / \    /  \
3   7  11  14
 \      
  4







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal