“Your root value can have any value between -∞ to + ∞, say it is 30 here, When you validate the right child of 30, it can take any value between 30 and + ∞. When you validate the left child of 30, it can take any value between — ∞ and 30. likewise

So the idea is Pass the minimum and maximum values between which the node’s value must lie.

First element in the preorder[] will definitely be the root, which is 20 here.

we start with the range minimum = Integer.MIN_VALUE and maximum = Interger.MAX_VALUE, so your root can take any value between this range.

So when putting the left node of 20(root), it must lie within the range to minimum = Integer.MIN_VALUE and maximum = 20, so check the next element in the preorder[], if it lies in this range, make it the left child to the root, else it must the the right chlid of the root and so on. See the figure for better understanding. ( see the execution sequence)

Solve it recursively.

Time Complexity: O(n)

Complete Code:

Output:

Inorder Traversal of Constructed Tree :
1 5 7 10 15 20 25 30 32 35 40

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

if we put the elements into a stack cant we solve it with below algorithm also. I think we dont have to return the min values since the preorder is always needs to be assumed as correct. What do you think

public boolean buildBSTFromPreOrder(Node pNode,Integer max,Stack nodes){