LeetCode 654 - Maximum Binary Tree

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Stack, Tree, Monotonic Stack, Binary Tree

Solution

Problem Understanding

The problem asks us to construct a maximum binary tree from a given integer array nums with unique elements. A maximum binary tree is a binary tree where each node is the maximum element of the subarray it represents. Specifically, the root of the tree is the largest element in the entire array. The left child of the root is the maximum binary tree of all elements to the left of this maximum, and the right child is the maximum binary tree of all elements to the right of this maximum.

The input is an integer array nums with constraints that all elements are unique and that the array length ranges from 1 to 1000. The output is the root of a binary tree that represents the maximum binary tree built according to the rules above. Each tree node has a value, a left child, and a right child, where either child can be None if there is no corresponding subtree.

Important edge cases include arrays of length 1 (the tree is just a single node), strictly increasing or strictly decreasing arrays (trees are skewed to the right or left, respectively), and arrays where the maximum appears at the edges.

The uniqueness guarantee simplifies the problem because we do not need to handle duplicates, which could otherwise complicate subtree decisions.

Approaches

The brute-force approach is to recursively find the maximum element in the current subarray, create a node with that value, and then recursively build left and right subtrees from the subarrays to the left and right of the maximum. This approach works because it directly implements the problem's recursive definition, but it is inefficient because finding the maximum requires scanning the subarray each time. For an array of length n, the first scan is O(n), the next left and right scans are smaller but still sum up to O(n^2) in the worst case, especially for sorted arrays.

A more optimal approach uses a monotonic stack. The insight is that we can construct the tree iteratively by maintaining a stack of nodes in decreasing order. For each element, we pop elements from the stack smaller than the current element and assign them as the left child of the current node. If the stack is not empty after this, the current node becomes the right child of the top of the stack. This ensures each node finds its correct parent in linear time because each element is pushed and popped at most once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Recursively find max in subarray; slow for sorted arrays
Optimal	O(n)	O(n)	Monotonic stack ensures each element is handled once

Algorithm Walkthrough

Initialize an empty stack to hold nodes.
Iterate through each element num in nums.
Create a new tree node node for num.
While the stack is not empty and the top node's value is smaller than num, pop it and assign it as node.left. This ensures the smaller elements become left children of the next larger element.
If the stack is not empty after popping, the top node's right child is set to node. This ensures node is correctly attached to its parent.
Push node onto the stack.
After processing all elements, the root of the tree is the first element in the stack (bottom-most element).

Why it works: The stack maintains a decreasing order of nodes, ensuring that when a new maximum arrives, all smaller nodes are attached to it as left children, preserving the maximum binary tree property. The final stack contains the hierarchy of parent-child relationships consistent with the maximum binary tree definition.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        stack = []
        for num in nums:
            node = TreeNode(num)
            while stack and stack[-1].val < num:
                node.left = stack.pop()
            if stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0] if stack else None

The implementation iterates through the array, maintaining a stack to track nodes whose parent is not yet determined. Smaller nodes are popped and assigned as the left child of the current node, while the remaining node on top of the stack (if any) becomes the parent of the current node.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    stack := []*TreeNode{}
    for _, num := range nums {
        node := &TreeNode{Val: num}
        for len(stack) > 0 && stack[len(stack)-1].Val < num {
            node.Left = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            stack[len(stack)-1].Right = node
        }
        stack = append(stack, node)
    }
    if len(stack) == 0 {
        return nil
    }
    return stack[0]
}

In Go, we handle slices instead of Python lists, and nil represents the absence of a child node. The logic mirrors the Python solution exactly, with popping implemented by reslicing the stack.

Worked Examples

Example 1: nums = [3,2,1,6,0,5]

Step	Stack Content	Action
3	[3]	Node 3 pushed
2	[3,2]	Node 2 pushed
1	[3,2,1]	Node 1 pushed
6	[6]	Pop 1,2,3 → all become left children of 6
0	[6,0]	Node 0 pushed
5	[6,5]	Pop 0 → node 0 becomes left of 5, 5 becomes right of 6

Example 2: nums = [3,2,1]

Step	Stack Content	Action
3	[3]	Node 3 pushed
2	[3,2]	Node 2 pushed
1	[3,2,1]	Node 1 pushed

Final tree has root 3, right child 2, and right grandchild 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is pushed and popped from the stack at most once
Space	O(n)	Stack holds at most `n` nodes at any point; recursive stack avoided

The monotonic stack allows linear time construction without recursion depth overhead, which is important for large arrays.

Test Cases

# Provided examples
assert Solution().constructMaximumBinaryTree([3,2,1,6,0,5]).val == 6  # root is 6
assert Solution().constructMaximumBinaryTree([3,2,1]).val == 3         # root is 3

# Single element
assert Solution().constructMaximumBinaryTree([10]).val == 10           # root is 10

# Increasing order
root = Solution().constructMaximumBinaryTree([1,2,3,4])
assert root.val == 4 and root.left is not None                        # root 4, left skewed tree

# Decreasing order
root = Solution().constructMaximumBinaryTree([4,3,2,1])
assert root.val == 4 and root.right is None                           # root 4, right skewed tree

# Random order
root = Solution().constructMaximumBinaryTree([2,5,1,7,3])
assert root.val == 7                                                   # root is max element 7

Test	Why
`[3,2,1,6,0,5]`	Standard case with root in the middle
`[3,2,1]`	Right-skewed tree
`[10]`	Single element
`[1,2,3,4]`	Left-skewed tree, increasing order
`[4,3,2,1]`	Right-skewed tree, decreasing order
`[2,5,1,7,3]`	Random order, checks correct parent-child assignment

Edge Cases

The first edge case is an array with a single element. This is a potential source of off-by-one errors because there are no subarrays. Our solution correctly returns a single node without any children.

The second edge case is a strictly increasing array, which produces a left-skewed tree. A naive recursive solution may inefficiently scan each subarray repeatedly, but the stack-based approach handles this linearly because each element becomes the left child of the next larger one.

The third edge case is a strictly decreasing array, which produces a right-skewed tree. The monotonic stack ensures that no left children are assigned and each node is connected as the right child of its predecessor, avoiding unnecessary recursive calls or incorrect tree structures