Maximum Binary Tree

The key idea

The maximum of any range is its subtree's root, and it splits the range into a left and right part. A monotonic decreasing stack lets you build the whole tree in one left-to-right pass: each new value pops every smaller value to become their parent on the right.

Problem

You are given an integer array nums with no duplicates. A maximum binary tree is built recursively from nums using the following rules:

1. The root is the maximum value in nums.
2. The left subtree is the maximum binary tree built from the part of nums to the left of the maximum value.
3. The right subtree is the maximum binary tree built from the part of nums to the right of the maximum value.

Return the maximum binary tree built from nums. An empty part builds an empty subtree (null).

Constraints

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
All integers in nums are unique.

Examples

Input: nums = [3,2,1,6,0,5] Output: [6,3,5,null,2,0,null,null,1]

Input: nums = [3,2,1] Output: [3,null,2,null,1]

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →