Max Tree non-recursion solution

Question

from lintcode

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

The root is the maximum number in the array
The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.

Example
Given [2, 5, 6, 0, 3, 1], the max tree constructed by this array is:

    6
   / \
  5   3
 /   / \
2   0   1

Idea

Last time I showed how to solve this question with recursion, which I believe the best in terms of maintainability and understandability. BUT, you can also try to use a stack mimic the recursive behaviour, with a little bit more code.

The key here is this: If the inserted element is greater than root, very easy, just put the whole tree under the left of the inserted element. If not, you have to look down the right branch of the tree and find a node which is greater than the element, then you have to cut the branch, and connected it back after the branch merges with the inserted element (the branch root might be replaced by the inserted element).

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

// My recursive solution is simpler. Check that out.
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
        TreeNode root = null;
        for(int x : A) {
            TreeNode xnode = new TreeNode(x);
            if (root == null) {
              root = xnode;
              continue;
            }
            if (root.val < x) {
                TreeNode newRoot = xnode;
                newRoot.left = root;
                root = newRoot;
                continue;
            } else {
                Stack<TreeNode> stack = new Stack<>();
                stack.push(root);
                // root > x, will never be poped
                // guaranteed that stack has at least root
                while(true) {
                    TreeNode subtree = stack.peek();
                    if (subtree.val < xnode.val) {
                        xnode.left = subtree;
                        stack.pop();
                        // you can assert that stack.peek() is NEVER null (root is never poped)
                        break;
                    } else {
                        if (subtree.right == null) break;
                        stack.push(subtree.right);
                    }
                }
                stack.peek().right = xnode;
            }
        }
        return root;
    }
}