> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/construct-bst-from-postorder.md).

# Construct BST from Postorder

Given postorder traversal of a Binary Search Tree, you need to complete the function **constructTree()** which will create a BST. The output will be the inorder of the constructed BST.

**Input:**\
The constructTree() method consist of two arguments as input, the array consisting of the **post order traversal** and the **size of the array**.

**Output:**\
Print the Inorder traversal of the constructed BST.

**Constraints:**\
1 <= T <= 100\
1 <= N <= 100

**Example:**\
**Input:**\
2\
6\
1 7 5 50 40 10\
9\
216 823 476 429 850 93 18 975 862

**Output:**\
1 5 7 10 40 50\
18 93 216 429 476 823 850 862 975

**Explanation:**\
**Testcase 1:** The BST for the given post order traversal is:<br>

![](https://www.cdn.geeksforgeeks.org/wp-content/uploads/BST.jpg)

Thus the inorder traversal of BST is: 1 5 7 10 40 50.

```java
// Naive Solution -> O(N*N)
// Go to every node & find the split in the array and call recursively

// O(N) -> Solution
// Call right side first and maintain a global index, so that when it comes back to root node,
// it will be pointing to the split for left subtree.
// Now to maintain & check the BST order, we will mainatin upper & lower bounds.
class Solution {
    int index;

    public Node constructTree(int post[], int n) {
        index = n - 1;
        return helper(post, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public Node helper(int[] postOrder, int lowerBound, int upperBound) {
        if (index < 0 || (postOrder[index] < lowerBound || postOrder[index] > upperBound))
            return null;
        Node root = new Node(postOrder[index--]);
        root.right = helper(postOrder, root.data + 1, upperBound);
        root.left = helper(postOrder, lowerBound, root.data - 1);
        return root;
    }
}
```