Maximum Binary Tree
Understanding the Problem
We construct a binary tree from an array using one rule: the root of any subtree is the maximum element in the current subarray, the elements to its left form the left subtree, and the elements to its right form the right subtree.
This is 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 on where the maximums fall relative to each other.
This construction produces a Cartesian tree: a tree that satisfies the heap property on values (every parent is larger than its children) and the binary-search-tree property on the original array indices (left descendants come from indices before the root, right descendants from indices after). Those two properties together pin down a unique tree, which is why the array maps to exactly one maximum binary tree.
Key Constraints:
1 <= nums.length <= 1000-- With n up to 1000, an O(n^2) recursive solution runs in at most about a million operations, well within limits. An O(n) monotonic-stack solution also exists, which we cover as the second approach.0 <= nums[i] <= 1000-- All values fit comfortably in a 32-bit integer, so there is no overflow concern in any language.- All integers are unique -- There are no ties to break when finding the maximum, so the tree structure is uniquely determined.
Approach 1: Recursive Divide and Conquer
Intuition
The definition is itself recursive, so it translates directly into code: find the maximum, make it the root, and recurse on the two halves around it.
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.
This is correct because the maximum binary tree of any subarray is defined as exactly this: 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. The code is a literal transcription of that definition.
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 rescans the subarray for the maximum at every level. The next approach removes that repeated work and builds the entire tree in a single left-to-right pass.
Approach 2: Monotonic Stack (Optimal)
Intuition
Instead of repeatedly scanning for maximums, we process the array from left to right and keep a stack holding the right spine of the tree built so far: the path from the current root down through successive right children. The values on the stack decrease from bottom to top.
When a new value is smaller than the value on top of the stack, it becomes the right child of the top. When a new value is larger, we pop the smaller nodes off the stack. The last node popped becomes the left child of the new node, because those popped elements sit to the left of the new element in the array and are all smaller than it. If the stack is not empty after popping, the new node becomes the right child of the current top.
Each element is pushed once and popped at most once, so the total time is O(n).
The stack always equals the right spine of the partial tree: each node is the right child of the one below it. The invariant is that when we reach index i, the stack holds, bottom to top, the chain of maximums over the suffixes of nums[0..i-1]. A node x on the stack is the parent of everything popped above it because those popped values are smaller than x and lie between x's index and i, so within their own subarray x (or the new element) is the larger boundary. Moving the last popped node to the new node's left child preserves the index ordering: every element popped came before the new element in the array, so it belongs in the left subtree.
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).