/**

* public class TreeNode {

* public int key;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int key) {

* this.key = key;

* }

* }

*/

public class Solution {
  public TreeNode reconstruct(int[] post) {
    // there is no duplicate in the binary search tree.
    // traversing position of the post order, we traverse and construct the binary search tree from the postorder right to left
    // Write your solution here.

    if (post == null || post.length == 0) {

      return null;

    }

    int[] index = {post.length - 1};

    return helper(post,index, Integer.MIN_VALUE);
  }


  private TreeNode helper(int[] post, int[] index, int min) {
    // since it is binary search tree,  the "min" is actually the root, and we are using the root value to determine the boundary of //left/right subtree.  for right subtree, root is the min.
    // base case

    if (index[0] < 0 || post[index[0]] < min) {

      return null;

    }


    TreeNode root = new TreeNode(post[index[0]--]);


    root.right = helper(post, index, root.key);

    root.left = helper(post, index, min);

    return root;
  }
}