Maximum Binary Tree
Medium · Arrays & Hashing · Array · Divide and Conquer · Stack · Tree · Monotonic Stack · Binary Tree
Problem
You are given an integer array nums with no duplicate values. Build a maximum binary tree from it recursively:
- The root holds the largest value in the array.
- The left subtree is the maximum binary tree built from the values to the left of that value.
- The right subtree is the maximum binary tree built from the values to the right of that value.
An empty range gives no node. Return the root of the tree built from all of nums. The tree is shown in level order, with null for a missing child.
Examples
Input: nums = [1,4,2,5,3] Output: [5,4,3,1,2]
5 is the root; [1,4,2] builds the left subtree rooted at 4 (with 1 on its left and 2 on its right), and [3] is the right child.
Input: nums = [2,1] Output: [2,null,1]
2 is the root with nothing on its left, and 1 is its right child.
Input: nums = [3,2,1,6,0,5] Output: [6,3,5,null,2,0,null,null,1]
6 splits the array into [3,2,1] and [0,5]. Each side repeats the rule.
Constraints
- 1 <= len(nums) <= 1000
- 0 <= nums[i] <= 1000
- All values in nums are distinct
Approaches
- Recursive split at the maximum — time O(n²) worst, O(n log n) on average, space O(n)
Follow-up
If you only need each value’s parent or depth, you do not need nodes at all: the nearest greater values on both sides answer it. See the use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
