Construct BST from Preorder Traversal

Moderate
0/80
Average time to solve is 13m
profile
Contributed by
55 upvotes
Asked in companies
Samsung R&D InstituteMercer MettlTekion Corp

Problem statement

You are given a preorder traversal of a binary search tree. Your task is to find the postorder from the preorder.


Return the root of the BST constructed from the given preorder. The driver code will then use this root to print the post-order traversal.


For example: 
You are given preOrder = [10, 5, 1, 7, 40, 50], the binary search tree from the given preorder traversal is

sample1

Hence the answer is [1, 7, 5, 50, 40, 10].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘N’ representing the size of the preorder array.

The second line contains ‘N’ space-separated integers representing the preorder traversal of the tree.
Output Format: 
The only line contains the postorder of the BST constructed from the given preorder.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1
6
8 5 1 7 10 12
Sample Output 1:
1 7 5 12 10 8
Explanation:
preOrder = [8, 5, 1, 7, 10, 12], the binary search tree from the given preorder traversal is

sample2

Hence the answer is [1, 5, 7, 10, 40, 50].
Sample Input 2:
3
1 3 2
Sample Output 2:
2 3 1
Constraints:
 1 <= N <= 10^5
 1 <= preorder[i] <= 10^6

Time Limit: 1 sec.
Hint

Try using recursion

Approaches (2)
Recursive Approach

In this approach, it can be observed that the first element of the preorder array will always be the root of the BST. We can then note that all the elements after the first element, which are less than the root, will be in the left subtree of the root, and all the elements that are larger than the root will be in the right subtree of the root.

Therefore for each root, we create two arrays leftPreOrder, rightPreOrder, then divide the elements of the preOrder traversal into two arrays according to whether the elements are greater than the root element or not.

 

We will create recursive function util(preOrder), here preOrder is the preOrder traversal of the tree. 

 

Algorithm:

  • In the function util(preOrder)
    • If the size of preOrder is 0 return Null
    • Set root as TreeNode(preOrder[0])
    • Set leftPreOrder as the array with all the elements of preOrder that are smaller than preOrder[0]
    • Set rightPreOrder as the array with all the elements of preOrder that are smaller than preOrder[0]
    • Set root.left as util(leftPreOrder)
    • Set root.right as util(rightPreOrder)
  • Return util(preOrder)
Time Complexity

O(N^2), Where ‘N’ is the number of nodes in the tree.

 

We are iterating over each element in the preorder array, and for each element, we are dividing the array into two subarrays, which will cost O(N^2) time. Hence the final time complexity is O(N^2).

Space Complexity

O(N^2), Where ‘N’ is the number of nodes in the tree.

 

The recursion stack will take O(N) space. For each recursive call, we make two arrays that. will take O(N) space each. Hence the overall space complexity is O(N^2).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Construct BST from Preorder Traversal
Full screen
Console