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:

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

// 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;
    }
}