Maximum Binary Tree
Last Updated: April 1, 2026
Understanding the Problem
We need to construct a binary tree from an array using a specific rule: the root of any subtree is always the maximum element in the current subarray, and the elements to its left and right form the left and right subtrees respectively.
This is essentially a divide and conquer problem. At each level of recursion, we pick the maximum element as the root, then split the array around it. The structure of the resulting tree depends entirely on where the maximums fall relative to each other.
The key observation is that this construction is closely related to a data structure called a Cartesian tree, where the tree maintains both heap property (parent is larger than children) and BST property on array indices (left children come from indices before the root, right children from indices after).
Key Constraints:
1 <= nums.length <= 1000-- With n up to 1000, even an O(n^2) brute force is perfectly fine. We have at most ~1 million operations. But an O(n) approach exists using a monotonic stack.0 <= nums[i] <= 1000-- All values are non-negative. No special handling for negatives needed.- All integers are unique -- No ties to break when finding the maximum. This simplifies the logic and guarantees a unique tree structure.
Approach 1: Recursive Divide and Conquer
Intuition
The problem definition practically hands us the algorithm. We need to find the maximum, make it the root, and recurse on both sides. So the most natural approach is a direct recursive implementation of the construction rules.
At each step, we scan the current subarray to find the index of the maximum value. That maximum becomes the root node. Everything to its left in the array forms the left subtree, and everything to its right forms the right subtree. We recurse until the subarray is empty.
The reason this works is that the definition itself is recursive. The maximum binary tree of any subarray is: the max as root, with the maximum binary tree of the left portion as the left child and the maximum binary tree of the right portion as the right child. It is a textbook divide and conquer pattern.
Algorithm
- If the current subarray range is empty (left > right), return null.
- Scan the subarray from left to right to find the index of the maximum element.
- Create a new tree node with the maximum value.
- Recursively build the left subtree using elements from
lefttomaxIndex - 1. - Recursively build the right subtree using elements from
maxIndex + 1toright. - Return the root node.
Example Walkthrough
Code
- Time Complexity: O(n^2). In the worst case (sorted array), each recursive call scans the entire remaining subarray. The sum is n + (n-1) + ... + 1 = O(n^2). On average with random input, the expected time is O(n log n).
- Space Complexity: O(n). The recursion depth can be up to n in the worst case (sorted array producing a skewed tree).
The recursive approach mirrors the problem definition directly, but it rescans the subarray for the maximum at every level of recursion. What if we could build the entire tree in a single left-to-right pass?
Approach 2: Monotonic Stack (Optimal)
Intuition
Instead of repeatedly scanning for maximums, we can process the array from left to right and use a stack to maintain the "right spine" of the tree built so far. The stack holds nodes in decreasing order of value.
When a new value arrives that is smaller than the top, it becomes the right child of the top. When a new value is larger, we pop smaller nodes off the stack. The last popped node becomes the left child of our new node (because those smaller elements sit to the left of it in the array). If the stack is not empty after popping, our new node becomes the right child of the current top.
Each element is pushed exactly once and popped at most once, giving us O(n) total time.
The monotonic stack maintains a decreasing sequence of node values from bottom to top, which corresponds exactly to the rightmost path from the root downward in the tree built so far. When a new element is smaller than the top, it simply extends this right spine downward. When a new element is larger, it "absorbs" smaller elements into its left subtree, because in the original array those smaller elements sit to the left of the new element and are smaller, meaning the new element is their local maximum.
Algorithm
- Create an empty stack that will hold tree nodes.
- Iterate through each element in
numsfrom left to right. - Create a new tree node for the current element.
- While the stack is not empty and the top of the stack has a smaller value than the current element, pop from the stack. The last popped node becomes the left child of the current node.
- If the stack is not empty, the current node becomes the right child of the top of the stack.
- Push the current node onto the stack.
- After processing all elements, the bottom of the stack is the root of the tree.
Example Walkthrough
Code
- Time Complexity: O(n). Each element is pushed onto the stack once and popped at most once. Across all n elements, we do at most 2n stack operations, each O(1).
- Space Complexity: O(n). The stack can hold up to n elements in the worst case (when the input is sorted in decreasing order).