LeetCode 654: Maximum Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 654: Maximum Binary Tree?

In LeetCode 654: Maximum Binary Tree, you’re given an integer array nums with no duplicates, and your task is to construct a maximum binary tree where:

• The root is the maximum value in the array.
• The left child is the maximum binary tree of the subarray to the left of the maximum.
• The right child is the maximum binary tree of the subarray to the right of the maximum.

Return the root node of this tree. For example, with nums = [3, 2, 1, 6, 0, 5], the maximum is 6, so the root is 6, the left subarray [3, 2, 1] forms a subtree with root 3, and the right subarray [0, 5] forms a subtree with root 5. This problem tests your ability to recursively or iteratively build a tree based on array maximums.

Problem Statement

• Input:
• nums: List of unique integers.
• Output: Root node of the maximum binary tree.
• Rules:
• Root = maximum value in current subarray.
• Left child = maximum binary tree of left subarray.
• Right child = maximum binary tree of right subarray.

Constraints

• 1 ≤ nums.length ≤ 1000.
• 0 ≤ nums[i] ≤ 10⁹.
• 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] (Root 6, left 3, right 5, etc.)
• Input: nums = [3, 2, 1]
• Output: [3, 2, null, 1] (Root 3, left 2, left of 2 is 1)
• Input: nums = [1]
• Output: [1] (Single node)

These examples set the array—let’s solve it!

Understanding the Problem: Building the Tree

To solve LeetCode 654: Maximum Binary Tree in Python, we need to construct a binary tree from an array by repeatedly finding the maximum value as the root, splitting the array at that point, and building left and right subtrees recursively or iteratively. A brute-force approach—scanning the array for each subtree—would still work but could be optimized. Since the tree structure depends on maximums, we can use divide-and-conquer or stack-based methods. We’ll explore:

• Best Solution (Recursive Divide-and-Conquer): O(n log n) average time, O(h) space—fast and intuitive (h = height).
• Alternative Solution (Iterative with Stack): O(n) time, O(n) space—linear but complex.

Let’s start with the recursive solution, breaking it down for beginners.

Best Solution: Recursive Divide-and-Conquer

Why This Is the Best Solution

The recursive divide-and-conquer approach is the top choice for LeetCode 654 because it’s efficient—O(n log n) average time with O(h) space—and naturally follows the problem’s definition by splitting the array at each maximum, recursively building subtrees. It fits constraints (n ≤ 1000) well and is easy to understand once you see the recursion in action. It’s like carving the array into perfect tree pieces!

How It Works

Think of this as a tree carver:

• Step 1: Find Maximum:
• Identify the max value and its index in the current subarray.
• Step 2: Create Node:
• Make a node with the max value as the root.
• Step 3: Recurse:
• Left child = max tree of subarray left of max index.
• Right child = max tree of subarray right of max index.
• Step 4: Return Root:
• Return the constructed root node.

It’s like a max splitter—divide and build!

Step-by-Step Example

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

• Step 1: Full array:
• Max = 6, index = 3.
• Root = 6.
• Left = [3, 2, 1], Right = [0, 5].
• Step 2: Left [3, 2, 1]:
• Max = 3, index = 0.
• Node = 3.
• Left = [], Right = [2, 1].
• Right [2, 1]:
• Max = 2, index = 0.
• Node = 2.
• Left = [], Right = [1].
• Right [1]: Node = 1.
• Step 3: Right [0, 5]:
• Max = 5, index = 1.
• Node = 5.
• Left = [0], Right = [].
• Left [0]: Node = 0.
• Step 4: Tree: [6, 3, 5, null, 2, 0, null, null, 1].
• Output: Root node of this tree.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass 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]) -> TreeNode:
        # Step 1: Helper to build tree recursively
        def build(start: int, end: int) -> TreeNode:
            if start > end:
                return None

            # Find maximum value and index
            max_val = float('-inf')
            max_idx = start
            for i in range(start, end + 1):
                if nums[i] > max_val:
                    max_val = nums[i]
                    max_idx = i

            # Create root node with max value
            root = TreeNode(max_val)

            # Recurse on left and right subarrays
            root.left = build(start, max_idx - 1)
            root.right = build(max_idx + 1, end)

            return root

        # Step 2: Start with full array
        return build(0, len(nums) - 1)

• Lines 1-6: TreeNode class (standard).
• Lines 10-27: build:
• Base case: Empty subarray returns None.
• Find max value and index in range.
• Create root, recurse on left and right subarrays.
• Line 30: Start with full array.
• Time Complexity: O(n log n) average—n nodes, O(n) to find max, log n depth typically.
• Space Complexity: O(h)—recursion stack (h ≈ log n for balanced).

This is like a tree sculptor—split and shape!

Alternative Solution: Iterative with Stack

Why an Alternative Approach?

The iterative with stack approach builds the tree linearly—O(n) time, O(n) space. It’s more complex, using a stack to track nodes and adjust children, but avoids recursion overhead. It’s like stacking blocks to form the tree step-by-step!

How It Works

Picture this as a stack builder:

• Step 1: Init stack.
• Step 2: Iterate array:
• For each num:
• Pop smaller nodes from stack, set as right children.
• Push num as new node, set left to last popped (if any).
• Step 3: Return stack bottom (root).

It’s like a stack assembler—push and link!

Step-by-Step Example

Example: Same as above

• Step 1: Stack = [].
• Step 2: Iterate:
• 3: Stack = [3].
• 2: 2 < 3, Stack = [3, 2], 3.left = 2.
• 1: 1 < 2, Stack = [3, 2, 1], 2.left = 1.
• 6: Pop 1, 2, 3 (6 > all), 3.right = 6, Stack = [6].
• 0: 0 < 6, Stack = [6, 0], 6.left = 0.
• 5: 5 > 0, pop 0, 0.right = 5, Stack = [6, 5], 6.left = 5.
• Step 3: Root = 6.
• Output: Same tree structure.

Code for Iterative Approach

Copy codeclass Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        # Step 1: Initialize stack
        stack = []

        # Step 2: Iterate array
        for num in nums:
            node = TreeNode(num)
            last_popped = None

            # Pop smaller nodes, set as right children
            while stack and stack[-1].val < num:
                last_popped = stack.pop()

            # Set left child to last popped (if any)
            node.left = last_popped

            # Push new node
            if stack:
                stack[-1].right = node
            stack.append(node)

        # Step 3: Return root (bottom of stack)
        return stack[0] if stack else None

• Line 4: Init empty stack.
• Lines 7-19: Iterate:
• Create node, pop smaller, link left/right, push node.
• Line 22: Return root.
• Time Complexity: O(n)—each node pushed/popped once.
• Space Complexity: O(n)—stack size.

It’s a stack linker—build and adjust!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(n log n) avg time, O(h) space, intuitive.
• Cons: Recursion overhead.
• Iterative (Alternative):
• Pros: O(n) time, O(n) space, linear.
• Cons: Stack logic less obvious.

Recursive wins for clarity.

Additional Examples and Edge Cases

• Input: [1]
• Output: [1].
• Input: [2, 1]
• Output: [2, 1].

Both handle these well.

Complexity Breakdown

• Recursive: Time O(n log n) avg, Space O(h).
• Iterative: Time O(n), Space O(n).

Iterative is theoretically faster, recursive simpler.

Key Takeaways

• Recursive: Divide-and-conquer—smart!
• Iterative: Stack assembly—clear!
• Trees: Building is fun.
• Python Tip: Recursion rocks—see Python Basics.

Final Thoughts: Build That Tree

LeetCode 654: Maximum Binary Tree in Python is a fun tree challenge. Recursive divide-and-conquer offers clarity and efficiency, while iterative stack provides a linear alternative. Want more? Try LeetCode 105: Construct Binary Tree from Preorder and Inorder or LeetCode 108: Convert Sorted Array to BST. Ready to construct? Head to Solve LeetCode 654 on LeetCode and build that tree today!