Problem Description

You need to build a special type of binary tree called a "maximum binary tree" from an integer array nums that contains no duplicate values.

The construction follows these rules:

1. Find the maximum value in the current array nums - this becomes the root node
2. Split the array into two parts at the position of the maximum value:
   • Everything to the left of the maximum becomes the left subarray
   • Everything to the right of the maximum becomes the right subarray
3. Recursively build the left subtree using the left subarray (following the same rules)
4. Recursively build the right subtree using the right subarray (following the same rules)
5. Continue this process until all elements are placed in the tree

For example, given nums = [2, 1, 6, 3]:

• The maximum is 6, so it becomes the root
• Left of 6 is [2, 1] - this forms the left subtree
  • Maximum of [2, 1] is 2, which becomes the left child
  • Left of 2 is empty, right of 2 is [1]
  • 1 becomes the right child of 2
• Right of 6 is [3] - this forms the right subtree
  • 3 becomes the right child of 6

The solution uses a recursive approach where for each call:

• It finds the maximum value in the current array segment
• Creates a node with that maximum value
• Recursively constructs left and right subtrees from the appropriate array segments
• Returns the constructed tree rooted at the maximum value node

The base case occurs when the array is empty, returning None to indicate no node should be created.

Intuition

The key insight is recognizing that this problem has a natural recursive structure. When we pick the maximum element as the root, we're essentially dividing the problem into two smaller, independent subproblems - building the left and right subtrees.

Think about it this way: once we place the maximum value at the root, all elements to its left in the original array must go into the left subtree, and all elements to its right must go into the right subtree. This is because we need to preserve the relative ordering of elements.

Why does this recursive pattern work? Consider what happens at each level:

• The maximum element naturally becomes the root because that's the rule
• The elements are already partitioned by their position relative to the maximum
• Each partition (left and right) is just a smaller version of the same problem

This leads us to a divide-and-conquer approach:

1. Find the maximum (this is our pivot point)
2. Divide the array at this pivot
3. Conquer by recursively solving for each half

The beauty of this approach is that finding the maximum and splitting the array gives us everything we need for the current node, and we can trust recursion to handle the rest. Each recursive call handles a smaller array segment, eventually reaching empty arrays (our base case).

The pattern find max → create node → split array → recurse on both parts naturally builds the tree structure we want, with larger values closer to the root and the original array's relative ordering preserved in the tree's in-order traversal.

Learn more about Stack, Tree, Divide and Conquer, Binary Tree and Monotonic Stack patterns.

Solution Approach

The implementation uses a recursive helper function dfs to construct the maximum binary tree. Let's walk through the implementation step by step:

Base Case:

if not nums:
    return None

When the array is empty, we return None to indicate no node should be created. This happens when we've processed all elements in a subarray.

Finding the Maximum and Its Position:

val = max(nums)
i = nums.index(val)

We find the maximum value in the current array using max(nums) and locate its position using nums.index(val). This gives us both the value for our current node and the split point for dividing the array.

Creating the Current Node:

root = TreeNode(val)

We create a new tree node with the maximum value. This node will serve as the root for the current subtree.

Recursive Construction:

root.left = dfs(nums[:i])
root.right = dfs(nums[i + 1:])

• nums[:i] creates a slice containing all elements before the maximum (left subarray)
• nums[i + 1:] creates a slice containing all elements after the maximum (right subarray)
• We recursively call dfs on each subarray to build the left and right subtrees

Array Slicing Pattern: The solution uses Python's array slicing to partition the data:

• If maximum is at index i, elements [0...i-1] go to the left subtree
• Elements [i+1...n-1] go to the right subtree
• The element at index i becomes the current node

Time Complexity: O(n²) in the worst case (when the array is sorted), where finding the maximum takes O(n) and we do this for each element. In the best case (balanced partitions), it's O(n log n).

Space Complexity: O(n) for the recursion stack in the worst case, plus the space for array slices.

The elegance of this solution lies in its direct translation of the problem requirements into code - each recursive call handles exactly one node and delegates the subtree construction to recursive calls.

Example Walkthrough

Let's trace through the algorithm with nums = [3, 2, 1, 6, 0, 5] to see how the maximum binary tree is constructed.

Initial Call: dfs([3, 2, 1, 6, 0, 5])

• Find max: 6 at index 3
• Create root node with value 6
• Split array:
  • Left subarray: [3, 2, 1] (indices 0-2)
  • Right subarray: [0, 5] (indices 4-5)
• Recursively build left and right subtrees

Left Subtree: dfs([3, 2, 1])

• Find max: 3 at index 0
• Create node with value 3
• Split array:
  • Left subarray: [] (empty)
  • Right subarray: [2, 1] (indices 1-2)
• Left child is None (empty array)
• Recursively build right subtree

Processing [2, 1]:

• Find max: 2 at index 0
• Create node with value 2
• Split: left [], right [1]
• Left child is None
• Right child: dfs([1]) creates node with value 1 (no further splits needed)

Right Subtree: dfs([0, 5])

• Find max: 5 at index 1
• Create node with value 5
• Split array:
  • Left subarray: [0] (index 0)
  • Right subarray: [] (empty)
• Left child: dfs([0]) creates node with value 0
• Right child is None

Final Tree Structure:

       6
      / \
     3   5
      \  /
       2 0
        \
         1

The algorithm correctly places the maximum value 6 at the root, with all elements originally to its left ([3, 2, 1]) in the left subtree and elements to its right ([0, 5]) in the right subtree. This pattern continues recursively at each level, maintaining the relative ordering of the original array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²) in the worst case, O(n log n) in the average case

• In each recursive call, we find the maximum element using max(nums) which takes O(n) time where n is the size of the current subarray
• We also use nums.index(val) to find the index, which takes another O(n) time
• The list slicing operations nums[:i] and nums[i+1:] each take O(n) time to create new lists
• In the worst case (when the array is sorted), the recursion tree is skewed:
  • The maximum is always at one end, creating a tree of depth n
  • At each level k, we process n-k elements
  • Total work: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)
• In the best/average case (balanced partitions), the recursion tree has depth O(log n):
  • Each level of the tree processes O(n) total elements
  • With O(log n) levels, total complexity is O(n log n)

Space Complexity: O(n²) in the worst case, O(n log n) in the average case

• The recursive call stack depth is O(n) in the worst case and O(log n) in the average case
• At each recursive call, we create new sublists through slicing:
  • Each slice creates a new list that requires space proportional to its size
  • In the worst case, we have O(n) recursive calls, and the total space for all slices is n + (n-1) + ... + 1 = O(n²)
  • In the average case with balanced partitions, we have O(log n) levels, and each level uses O(n) space for slices, resulting in O(n log n) space
• Additionally, the output tree itself requires O(n) space to store all nodes

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Maximum Finding in Each Recursive Call

The current solution uses max(arr) followed by arr.index(max_value), which requires two passes through the array - one to find the maximum and another to find its position. This is inefficient and contributes to the O(n²) worst-case complexity.

Problem Code:

max_value = max(arr)
max_index = arr.index(max_value)

Better Approach:

# Find max value and index in a single pass
max_index = 0
max_value = arr[0]
for i in range(1, len(arr)):
    if arr[i] > max_value:
        max_value = arr[i]
        max_index = i

2. Excessive Array Copying with Slicing

Creating new array slices (arr[:max_index] and arr[max_index + 1:]) for each recursive call creates unnecessary copies of the data, consuming O(n) extra space per level and adding to the time complexity.

Optimized Solution Using Index Boundaries:

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def build_tree(left: int, right: int) -> Optional[TreeNode]:
            # Work with indices instead of creating new arrays
            if left > right:
                return None
          
            # Find max in the range [left, right]
            max_index = left
            for i in range(left + 1, right + 1):
                if nums[i] > nums[max_index]:
                    max_index = i
          
            root = TreeNode(nums[max_index])
            root.left = build_tree(left, max_index - 1)
            root.right = build_tree(max_index + 1, right)
          
            return root
      
        return build_tree(0, len(nums) - 1)

3. Stack-Based O(n) Solution Not Considered

The recursive approach has O(n²) worst-case time complexity. There's a more efficient O(n) solution using a monotonic decreasing stack that many developers miss:

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        stack = []
      
        for num in nums:
            node = TreeNode(num)
            last = None
          
            # Pop smaller elements and make them left child
            while stack and stack[-1].val < num:
                last = stack.pop()
          
            node.left = last
          
            # Current node becomes right child of the last larger element
            if stack:
                stack[-1].right = node
          
            stack.append(node)
      
        return stack[0] if stack else None

This maintains a decreasing stack where each new element either becomes a right child of the stack top (if smaller) or pops elements to become their parent (if larger), achieving linear time complexity.