Construct BST from Post-order

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in companies
IntuitChegg Inc.D.E.Shaw

Problem statement

You have been given an array ‘postOrder’ consisting of ‘N’ elements. The array represents the post order traversal of a Binary Search Tree(BST). You need to construct the BST from this post order traversal.

Note: A Binary Search Tree (BST) is a binary tree data structure that has the following properties -

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

For Example:

For the given post order traversal: 2 4 3 7 6 5
The BST will be: 


The Inorder Traversal of this BST is 2 3 4 5 6 7.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer 'N', which denotes the number of nodes in the tree.

The second line of each test case contains ‘N’ single space-separated integers denoting the post-order traversal of the tree.
Output Format: 
For each test case, print the inorder traversal of the BST.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^5
0 <= postOrder[i] <= 10^5

Time Limit: 1 sec
Sample Input 1:
2
7
8 12 10 16 25 20 15
3
1 3 2
Sample Output 1:
8 10 12 15 16 20 25
1 2 3
Explanation of Sample Input 1:
Test Case 1: For the given post-order traversal, the BST can be represented as follows


The inorder traversal of this BST is 8 10 12 15 16 20 25.

Test Case 2: For the given post-order traversal, the BST can be represented as follows


The inorder traversal of this BST is 1 2 3.
Sample Input 2:
2 
2
10 5 
1
20
Sample Output 2:
5 10
20
Hint

Think of finding the position for every number by recursively traversing the tree.

Approaches (2)
Recursive Approach

The basic idea is to find the position of every node in the tree. The last element of the post order is always the root of the tree. The elements smaller than root should be present in the left subtree, and elements greater than root should be present in the right subtree to satisfy BST conditions. So, we find the last element index, which is smaller than the root, and divide the array to build the BST.

 

Here is the algorithm :
 

  1. Base case:
    • Check if the size of ‘postOrder’ is 0, return NULL.
  2. Call the ‘HELPER’ function.
     

HELPER(‘postORDER’, ‘LOW’, ‘HIGH’)  (where ‘postOrder’ is the given array, ‘LOW’ and ‘HIGH’ are indexes of the array initialized from 0 to ‘N’ - 1).  

 

  1. Base case:
    • Check if ‘LOW’ is greater than ‘HIGH’, return NULL.
  2. Create a new node (say, ‘ROOT’) with the initial value present at index ‘HIGH’.
  3. Run a loop from ‘HIGH’ to ‘LOW’ (say, iterator ‘i’) to find the last index with a value smaller than the root value.
    • Check if ‘postOrder[i]’ is smaller than the data of ‘ROOT’.
  4. Call HELPER function recursively with the value of ‘LOW’ updated to ‘i’ + 1, and ‘HIGH’ decremented by 1 and store the value returned by the function in right of ‘ROOT’.
  5. Similarly, call HELPER function recursively with the value of ‘HIGH’ updated to ‘i’ and store the value returned by the function in the left of ‘ROOT’.
  6. Finally, return ‘ROOT’.
Time Complexity

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

 

We traverse the array once to find the last index of the array smaller than the root, which can take O(N) time, and then build a tree recursively, which takes O(N) time. Therefore, the overall time complexity will be O(N^2).

Space Complexity

O(N), where ‘N’ is the number of nodes in the tree.

 

The recursive stack can contain at most ‘N’ nodes of the binary tree. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Construct BST from Post-order
Full screen
Console