Maximum Binary Tree: Recursive Array Partitioning

You are given an integer array nums with no duplicates. Build a maximum binary tree from it using this rule: the root is the maximum element, its left subtree is built recursively from elements to the left of the maximum, and its right subtree is built recursively from elements to the right.

This is LeetCode 654: Maximum Binary Tree, and it tests whether you can decompose an array into recursive subproblems using a natural pivot point. The maximum element splits the array into two halves, and you repeat the same logic on each half until nothing is left.

The approach: recursive divide and conquer

The algorithm mirrors how you might describe the tree out loud:

1. Find the maximum value in the current subarray. That value becomes the current node.
2. Everything to the left of that maximum forms the left subtree.
3. Everything to the right of that maximum forms the right subtree.
4. Recurse on both halves. When the subarray is empty, return None.

This is a classic divide and conquer pattern. The "divide" step is finding the max and splitting around it. The "conquer" step is recursively building the left and right subtrees. The "combine" step is wiring them together as children of the current node.

Python solution

def construct_maximum_binary_tree(nums):
    if not nums:
        return None

    max_val = max(nums)
    max_idx = nums.index(max_val)

    root = TreeNode(max_val)
    root.left = construct_maximum_binary_tree(nums[:max_idx])
    root.right = construct_maximum_binary_tree(nums[max_idx + 1:])

    return root

Line by line walkthrough

if not nums: Base case. When the subarray is empty, there is no node to create. Return None to signal that this side of the tree has no child.

max_val = max(nums): Scan the current subarray to find its maximum value. This value becomes the root of the current subtree.

max_idx = nums.index(max_val): Find the index of that maximum. You need the index to know where to split the array.

root = TreeNode(max_val): Create a tree node with the maximum value.

root.left = construct_maximum_binary_tree(nums[:max_idx]): Recurse on the left portion, everything before the maximum. The slice nums[:max_idx] contains all elements that should live in the left subtree.

root.right = construct_maximum_binary_tree(nums[max_idx + 1:]): Recurse on the right portion, everything after the maximum. The slice nums[max_idx + 1:] contains all elements that should live in the right subtree.

return root: Return the constructed node so the parent call can attach it as a child.

Visual walkthrough

Let's trace through nums = [3, 2, 1, 6, 0, 5] step by step to see how the tree gets built from the bottom up.

Each recursive call does the same thing: scan for the max, split, and recurse. The recursion bottoms out when a partition is empty. Then the nodes get wired together as the call stack unwinds.

Complexity analysis

Time depends on how balanced the splits are. If the maximum is always near the middle, you get O(n log n), similar to quicksort with good pivots. If the array is sorted (ascending or descending), the maximum is always at one end, giving O(n^2) because each level only removes one element.

Space is O(n) for the recursion stack in the worst case (a completely skewed tree) plus O(n) for the array slices. In a balanced case, the stack depth is O(log n).

Building blocks

Recursive array partitioning. The core technique is splitting an array around a special element and recursing on both sides. This is the same structural pattern you see in quicksort (partition around a pivot) and in building a BST from a sorted array (pick the middle as root). The key insight: whenever a problem says "the root is determined by some property of the subarray," you are looking at this pattern.

Tree construction from traversal-like data. Even though nums is not a traversal, it encodes the tree's structure implicitly. Each recursive call extracts one node and defines the boundaries for its children. This mirrors how you build a tree from preorder + inorder, except here the "root" is determined by the max rather than by position in a traversal sequence.

Edge cases

• Single element: The array has one value. It becomes the root with no children. Both recursive calls get empty arrays and return None.
• Sorted ascending: [1, 2, 3, 4, 5]. The max is always the last element, so every node only has a left child. The tree degenerates into a right-skewed chain (from the perspective of always picking the rightmost element). This is the O(n^2) worst case.
• Sorted descending: [5, 4, 3, 2, 1]. The max is always the first element, so every node only has a right child. Same O(n^2) worst case, just mirrored.
• Two elements: [a, b]. The larger one is the root and the smaller one is either the left or right child depending on their positions.

From understanding to recall

You just watched the algorithm split an array, find the max, and recurse on both sides. The logic is clean and the code is short. But there is a gap between understanding the idea and writing it from memory under time pressure.

The details that trip people up: remembering to use nums[:max_idx] (not nums[:max_idx - 1]), remembering that nums[max_idx + 1:] correctly handles the case where the max is at the end (it gives an empty list), and remembering that the base case is if not nums rather than checking for a single element.

Spaced repetition closes that gap. You write the solution from scratch at increasing intervals until the pattern is automatic. After a few reps, you will not need to think about whether the slice boundary is inclusive or exclusive. It will just be there.

Related posts

• Construct Binary Tree from Preorder and Inorder - Another tree construction problem where you identify the root and partition the remaining elements recursively
• Unique Binary Search Trees II: Generate All Valid BSTs - Uses a similar recursive split strategy, choosing each value as a potential root and building left and right subtrees
• Convert Sorted Array to BST: Divide and Conquer - The same divide and conquer skeleton, but the pivot is the middle element instead of the maximum