#654

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximum Binary Tree

Construct a maximum binary tree by recursively selecting the largest element and dividing the array into left and right subtrees, tracking state carefully.

array divide and conquer stack tree monotonic stack

Problem Statement

Given an integer array nums with unique elements, construct a maximum binary tree using this rule: the root is the largest element in the array, the left subtree is the maximum tree built from the subarray left of the root, and the right subtree is built from the subarray right of the root. Return the constructed tree.

For example, given nums = [3,2,1,6,0,5], the root is 6, the left subtree is built from [3,2,1], and the right subtree from [0,5]. Each subtree follows the same recursive rule, producing a tree that reflects the maximum values hierarchy.

Examples

Example 1

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

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

The recursive calls are as follow:

The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
Empty array, so no child.
The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
Empty array, so no child.
Only one element, so child is a node with value 1.
The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
Only one element, so child is a node with value 0.
Empty array, so no child.

Example 2

Input: nums = [3,2,1]

Output: [3,null,2,null,1]

Example details omitted.

Constraints

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

Solution Approach

Recursive Divide-and-Conquer

Find the maximum in the current array segment, make it the root node, and recursively construct left and right subtrees from the subarrays. Maintain array bounds to prevent index errors.

Monotonic Stack Optimization

Iterate through the array using a stack to maintain decreasing elements. When a new element is larger than the stack top, pop nodes and assign them as left children. This reduces repeated scans for the maximum, improving efficiency.

Tree Traversal Validation

After construction, verify the tree with preorder or inorder traversal to ensure each node respects the maximum binary tree property. This helps catch misassigned left or right children caused by index or recursion mistakes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) for simple recursion due to repeated max searches, but O(n) with a monotonic stack. Space complexity is O(n) for recursion stack or explicit data structures.

What Interviewers Usually Probe

Expect you to explain recursive subtree construction and element selection.
They may probe for iterative alternatives using a stack to reduce repeated max searches.
Clarification questions often focus on handling empty arrays or single-element subarrays.

Common Pitfalls or Variants

Common pitfalls

Not correctly partitioning the array, leading to misplaced children.
Repeatedly scanning for the maximum without optimization, causing O(n^2) time.
Ignoring edge cases like empty subarrays or single-element segments.

Follow-up variants

Construct a maximum binary tree from a linked list instead of an array.
Build a minimum binary tree by selecting the smallest element as root at each step.
Return the preorder or inorder traversal of the maximum binary tree without building it explicitly.

FAQ

What is the main pattern used in Maximum Binary Tree?

The problem follows a binary-tree traversal and state tracking pattern, recursively dividing the array based on the maximum element.

Can Maximum Binary Tree be built iteratively?

Yes, using a monotonic stack approach, which assigns left children when popping smaller elements, reducing redundant maximum searches.

What is the time complexity for simple recursive construction?

It is O(n^2) because each recursive call scans the subarray for the maximum element.

How do you handle empty subarrays in recursion?

Return null for empty subarrays to ensure the parent node has no child in that direction.

Are all elements in nums unique for this problem?

Yes, Maximum Binary Tree requires that all integers in nums are unique to define a clear maximum at each step.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(nums):
            if not nums:
                return None
            val = max(nums)
            i = nums.index(val)
            root = TreeNode(val)
            root.left = dfs(nums[:i])
            root.right = dfs(nums[i + 1 :])
            return root

        return dfs(nums)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(nums):
            if not nums:
                return None
            val = max(nums)
            i = nums.index(val)
            root = TreeNode(val)
            root.left = dfs(nums[:i])
            root.right = dfs(nums[i + 1 :])
            return root

        return dfs(nums)

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(nums):
            if not nums:
                return None
            val = max(nums)
            i = nums.index(val)
            root = TreeNode(val)
            root.left = dfs(nums[:i])
            root.right = dfs(nums[i + 1 :])
            return root

        return dfs(nums)

Continue Practicing

#1008 construct binary search tree from preorder traversal #889 construct binary tree from preorder and postorder traversal #108 convert sorted array to binary search tree