DSA problem
Maximum Binary Tree
You are given an integer array nums with no duplicates. A maximum binary tree built from nums is defined recursively: the root is the maximum value in nums. The left subtree is the maximum binary tree built from the prefix of nums to the left of the maximum value. The right subtree is the maximum binary tree built from the suffix to the right of the maximum value. Return the maximum binary tree built from nums.
This recursive definition is itself the divide-and-conquer algorithm. To build the tree for a range [l, r], we divide by finding the index idx of the maximum element in that range, conquer by recursively building the trees for [l, idx-1] and [idx+1, r], and combine by attaching the two sub-trees to a new root whose value is nums[idx]. The base case is an empty range, which yields a null subtree.
Locating the maximum in a range of length k costs O(k). Each level of the recursion processes the entire array exactly once across all of its calls. In the worst case the array is already sorted, producing a skewed tree of height n and an overall time complexity of O(n²). In the average case the tree is well-balanced and the cost drops to O(n log n). A monotonic-stack approach can achieve O(n) but obscures the divide-and-conquer structure; for clarity we present the canonical recursive implementation.
The recursion makes the structural invariant easy to see: every node holds a value greater than every value beneath it, because the recursive call works on a strictly smaller range and selects the maximum of that range as its root. This property is the defining feature of the data structure and falls out naturally from the recursion.
Examples
nums = [3,2,1,6,0,5][6,3,5,null,2,0,null,null,1]nums = [3,2,1][3,null,2,null,1]nums = [1,2,3][3,2,null,1]Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
- All integers in nums are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.