Last Updated: 27 Oct, 2021

Construct BST from Post-order

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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 :

Base case:
- Check if the size of ‘postOrder’ is 0, return NULL.
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).

Base case:
- Check if ‘LOW’ is greater than ‘HIGH’, return NULL.
Create a new node (say, ‘ROOT’) with the initial value present at index ‘HIGH’.
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’.
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’.
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’.
Finally, return ‘ROOT’.

Solve now

02 Approach

We maintain a range for each node such that the value of that node should lie between the range. The range for ‘ROOT’ can be initialized with a small number and with a large number. For a node in the subtree, we update the range by setting its max value to be data of ‘ROOT’ - 1 for the left subtree, whereas the min value for the right subtree would be data of ‘ROOT’ + 1.

Here is the algorithm :

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

HELPER(‘postORDER’, ‘IDX’, ‘minDATA’, ‘maxDATA’) (where ‘postOrder’ is the given array, ‘IDX’ is the index for traversing initialized with ‘N’ - 1, ‘minDATA’, and ‘maxDATA’ is the range of a node).

Base case:
- Check if ‘IDX’ is smaller than 0, return NULL.
Store the current value of the ‘postORDER’ array present at the ‘IDX’ index in a variable (say, ‘CURR’).
Check if ‘CURR’ is smaller than ‘minDATA’ or greater than ‘maxDATA’.
- Return NULL.
Create a new node (say, ‘ROOT’) with the initial value ‘CURR’.
Decrement ‘IDX’ by 1.
Call HELPER function recursively with the value of ‘minDATA’ updated to ‘CURR’ + 1 and store the value returned by the function in right of ‘ROOT’.
Similarly, call HELPER function recursively with the value of ‘maxDATA’ updated to ‘CURR’ - 1 and store the value returned by the function in the left of ‘ROOT’.
Finally, return ‘ROOT’.

Solve now