# JAVA O(N) Solution

• The idea is similar to using stack of mids, but I find it cleaner to understand.
(Key Idea) You can always see a node as a mid and find all its right and append to next node as a left.

2. Then you find its right which is exactly the same as building a tree from scratch, but having a limit of this node
3. Append to next node(new mid) as a left.
4. Find new mid's right.
5. Then again you have a left, repeat from step 3 until the end of nums.
``````class Solution {

int i = 0;

public TreeNode constructMaximumBinaryTree(int[] nums) {
i = 0;
return findRight(nums, Integer.MAX_VALUE);
}

private TreeNode findRight(int[] nums, int curMax){
if(i >= nums.length || nums[i] > curMax){
return null;
}

TreeNode root = new TreeNode(nums[i]);
i++;
while(i < nums.length && nums[i] <= curMax){
if(nums[i] > root.val){
TreeNode t = new TreeNode(nums[i]);
t.left = root;
root = t;
i++;
}

root.right = findRight(nums, root.val);
}
return root;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.