# Construct a BST from given postorder traversal using Stack

**Introduction**

In this article, we will learn how to construct a BST from a given postorder traversal using Stack. Such problems are really important to study and understand as they help us understand various concepts about __Binary Trees__.

Once you go through this article carefully, you will better understand __Binary Search Trees__, __Tree Traversals__, and __Stack__.

**Problem Statement**

Your task is to create a __Binary Search Tree__ from a given __Post Order Traversal__ using __Stack__. Print the __Inorder Traversal__ of the BST.

**Example**

Consider the given Post Order Traversal: {26, 46, 37, 69, 85, 71, 55}

The Inorder Traversal that should be printed is: {26, 37, 46, 55, 69, 71, 85}

The BST formed looks like this:

**Recommended: Try the question yourself first before moving on to the approach and solution code.**

**Approach and Explanation**

To solve the problem at hand, we have to perform __Inorder Traversal__ on the given __Post Order __array. The point of highlight is that, during Post Order traversal, the root node is always found at the end of the array. So keeping this in mind, we get the root of our BST. Now iteratively find the left and right child for each node.

The approach in this article discusses how to construct the BST from a given Post Order traversal array.

Follow these steps:

- Create a function to construct the BST (say
**constructBST**). This function will take the input array, which is the post order traversal, from the user. Let’s name it**postOrder.**The function also takes the size of this array.

- Declare a variable to store the root node (say
**rootNode**). Set the value for**rootNode**to the last element of**postOrder**(that is**postOrder[size-1]**)**.**

- Create a stack (say
**bstStk**) that will act as a buffer and hold the potential parent nodes.

- Push the
**rootNode**into the stack.

- Now iterate through the
**postOrder**array in reverse order. For each iteration, do:- Create a node (say
**x**) of the element at**postOrder[i]**.

- Create a temporary node (say
**tempNode**) and set its value to NULL.

- Now iterate while the stack is not empty and the element at
**postOrder[i]**is less than the element at the top of the stack.- If true, then set the value of
**tempNode**as the top of the stack and pop that element from the stack.

- If true, then set the value of
- Once the while loop is completed, check if the value of
**tempNode**is null or not.- If null then, set
**x**as the right child of the element at the top of the stack. - If not null then, set
**x**as the left child of**tempNode.**

- If null then, set
- Finally, push
**x**into the stack.

- Create a node (say
- Once the for loop is exhausted, print the root node. Call the
**printInorder()**function and pass**rootNode**so as to print the inorder traversal of the newly constructed BST.

**Java Implementation**

```
import java.util.Stack;
class BSTNode {
int data;
BSTNode leftChild, rightChild;
BSTNode(int data)
{
this.data = data;
leftChild = rightChild = null;
}
}
public class StackToBST {
void constructBST(int[] postOrder, int size)
{
BSTNode rootNode = new BSTNode(postOrder[size - 1]);
Stack<BSTNode> bstStk = new Stack<>();
bstStk.push(rootNode);
for (int i = size - 2; i >= 0; --i) {
BSTNode x = new BSTNode(postOrder[i]);
BSTNode tempNode = null;
while (!bstStk.isEmpty() && postOrder[i] < bstStk.peek().data) {
tempNode = bstStk.pop();
}
if (tempNode == null) {
bstStk.peek().rightChild = x;
} else {
tempNode.leftChild = x;
}
bstStk.push(x);
}
System.out.println("The Root node is: " + rootNode.data);
System.out.println("INORDER TRAVERSAL OF THE BST: ");
printInorder(rootNode);
}
void printInorder(BSTNode node)
{
if (node == null)
return;
printInorder(node.leftChild);
System.out.print(node.data + " ");
printInorder(node.rightChild);
}
public static void main(String[] args)
{
StackToBST tree = new StackToBST();
int[] postOrder = new int[] { 26, 46, 37, 69, 85, 71, 55};
int size = postOrder.length;
tree.constructBST(postOrder, size);
}
}
```

OUTPUT

```
The Root node is: 55
INORDER TRAVERSAL OF THE BST:
26 37 46 55 69 71 85
```

**Complexities**

**Time Complexity**

In the given approach, we select each element from the Post Order array and compare it with the top of the stack.

We use a loop of length ‘n’ to traverse the postorder array, and in each iteration, depending upon the value of the current element and those present in the stack, we perform push or pop operations. At first look, the complexity seems to be more than O(n).

But if you observe carefully, every element in the postorder array is pushed into and popped from the stack at most once. So, the total number of operations is roughly **2*n, and time** complexity turns out to be **O(2*n)** which is **O(n) **only.

**T(n) = O(n),**

where n is the size of the BST.

**Space Complexity**

In the given approach, we create a stack whose space is proportional to the height of the given BST at any instance.

Thus,

**Space Complexity = O(h),**

where h is the height of the BST.

**Frequently Asked Questions**

**What is a BST?**

A__Binary Search Tree__or BST is a special kind of__Binary Tree__where each node has two child nodes, and the nodes in the left subtree are smaller than the nodes in the right subtree. To know more about trees, visit our__CN Library | Free Online Coding Resources__.

**What is the difference between Post Order and Inorder Traversal?**

The order of traversal in Post Order Traversal is left, right, root. The order of traversal in Inorder Traversal is left, root, right. To know more about tree traversals visit,__Traversals__.

**Key Takeaways **

To summarize the article, we discussed how to construct a BST from a given postorder traversal using Stack. We saw the problem statement and an example. Then we saw an approach to our problem followed by a Java implementation and its time and space complexities. In the end, we discussed a few FAQs.

Want to improve your coding skills? Start practicing problems of various difficulty levels on our __CodeStudio__.

Want to learn about topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more? Visit __CN Library | Free Online Coding Resources__ today.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think