Construct a BST from given Postorder Traversal using Stack

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.
       
  • 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.
       
  • Finally, push x into the stack.
     
• 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);
  }
}

You can also try this code with Online Java Compiler

Run Code

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.

You can also read about insertion into 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. 

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. 

Conclusion

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.
 

Recommended Reading:

• Reverse a Stack using Recursion
• Construct a BST From Given Preorder Traversal
• Implementing Forward Iterator in BST
• Implementing Backward Iterator in BST
• Create A Wave Array From The Given Binary Search Tree
• Check For Identical BSTs Without Building the Trees
• Introduction to AVL Trees
• Insertion in AVL Tree
• Deletion in AVL Tree
• Insertion Searching and Deletion in AVL Trees Containing A Parent Node Pointer

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal

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

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

Happy Coding!