Max Tree

Explanation & pseudocode

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    public TreeNode maxTree(int[] A) {
        // write your code here
        if (A == null || A.length == 0) return null;
        TreeNode root = new TreeNode(A[0]);
        TreeNode curr;
        TreeNode prev = root;
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 1; i < A.length; i++) {
            curr = new TreeNode(A[i]);
            while (prev.val < curr.val && prev != root) {
                //last = parent(last)
                prev = stack.pop();
            }
            //The curr element is the smallest element yet, make it neww root
            if (prev.val < curr.val) {
                curr.left = prev;
                root = curr;
            //just insert it
            } else if (prev.right == null) {
                prev.right = curr;
                stack.push(prev);
            } else {
                curr.left = prev.right;
                prev.right = curr;
                stack.push(prev);
            }
            prev = curr;
        }
        return root;
    }
}