LeetCode 124: Binary Tree Maximum Path Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 124: Binary Tree Maximum Path Sum?

In LeetCode 124: Binary Tree Maximum Path Sum, you’re given the root of a binary tree, and your goal is to find the maximum path sum. A path is any sequence of nodes connected by edges, where each node is visited at most once, and it doesn’t have to pass through the root or end at a leaf. The path sum is the total of all node values along that path. For example, with root = [1, 2, 3], the maximum path sum is 6 (path 2 → 1 → 3).

Problem Statement

• Input: Root of a binary tree (TreeNode).
• Output: An integer—the maximum path sum in the tree.
• Rules:
• Path is a sequence of nodes connected by edges.
• Each node appears at most once in a path.
• Path can start and end anywhere, not necessarily root or leaf.

Constraints

• Number of nodes: 1 <= n <= 3 * 10⁴
• -1000 <= Node.val <= 1000

Examples

• Input: root = [1, 2, 3]
• Output: 6
• Why: Path 2 → 1 → 3 = 2 + 1 + 3 = 6.
• Input: root = [-10, 9, 20, None, None, 15, 7]
• Output: 42
• Why: Path 15 → 20 → 7 = 15 + 20 + 7 = 42.
• Input: root = [2, -1]
• Output: 2
• Why: Single node 2 is the best path.

Understanding the Problem: Finding the Golden Path

To solve LeetCode 124: Binary Tree Maximum Path Sum in Python, we need to identify the path with the highest sum, considering all possible paths—straight through a node, left-only, right-only, or a mix. A brute force approach—checking every possible path—would take O(n²) time, which is too slow for 3 * 10⁴ nodes. Instead, we’ll use smarter strategies:

• Best Solution (Recursive DFS): O(n) time, O(h) space—tracks max globally.
• Alternative Solution (Iterative DFS): O(n) time, O(h) space—uses a stack.

Let’s dive into the Best Solution—recursive DFS—and break it down step-by-step.

Best Solution: Recursive DFS with Global Tracking

Why This Is the Best Solution

The recursive DFS approach is the gold standard because it’s efficient—O(n) time—and intuitive once understood, using O(h) space (where h is the tree height) via the recursion stack. It explores every node once, tracking the maximum path sum globally while computing the best path contribution from each subtree. It’s like scouting every branch, keeping a running tally of the best treasure found—elegant and fast!

How It Works

Here’s the strategy:

• Step 1: Global Max:
• Use a global variable (or class attribute) to track the maximum path sum across all paths.
• Step 2: Recursive Function:
• max_gain(node): Returns the max sum of a path starting at node and going down one side (left or right).
• For each node:
• Get max gain from left and right subtrees (0 if negative or None).
• Update global max with the path through the node (left + node + right).
• Return node’s value plus the max of left or right (for parent’s path).
• Step 3: Kick Off:
• Start recursion from root, return global max.

Step-by-Step Example

Example: root = [-10, 9, 20, None, None, 15, 7]

• Tree:

-10 / \ 9 20 / \ 15 7

• Initialize: max_sum = -inf.
• Node 9:
• Left = Right = None, gain = 0.
• Path through 9 = 9.
• max_sum = max(-inf, 9) = 9.
• Return 9.
• Node 15:
• Left = Right = None, gain = 0.
• Path through 15 = 15.
• max_sum = max(9, 15) = 15.
• Return 15.
• Node 7:
• Left = Right = None, gain = 0.
• Path through 7 = 7.
• max_sum = 15.
• Return 7.
• Node 20:
• Left gain = 15, Right gain = 7.
• Path through 20 = 15 + 20 + 7 = 42.
• max_sum = max(15, 42) = 42.
• Return 20 + max(15, 7) = 20 + 15 = 35.
• Node -10:
• Left gain = 9, Right gain = 35.
• Path through -10 = 9 + (-10) + 35 = 34.
• max_sum = max(42, 34) = 42.
• Return -10 + max(9, 35) = -10 + 35 = 25 (not used).
• Result: 42.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # Step 1: Initialize global max
        self.max_sum = float('-inf')

        def max_gain(node):
            if not node:
                return 0

            # Step 2: Get max gain from subtrees
            left_gain = max(max_gain(node.left), 0)  # Ignore negative paths
            right_gain = max(max_gain(node.right), 0)

            # Step 3: Update global max with path through node
            current_path = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, current_path)

            # Step 4: Return max path for parent
            return node.val + max(left_gain, right_gain)

        max_gain(root)
        return self.max_sum

• Line 4: Global max_sum starts at negative infinity.
• Line 6-17: Recursive function:
• Line 8-9: Base case—return 0 for null.
• Line 11-12: Recurse on left and right, take max with 0.
• Line 15-16: Update global max with path through current node.
• Line 18: Return best single-path sum for parent.
• Line 20-21: Start recursion, return result.
• Time Complexity: O(n)—each node visited once.
• Space Complexity: O(h)—recursion stack, h is tree height.

This is a treasure-hunting DFS gem!

Alternative Solution: Iterative DFS with Stack

Why an Alternative Approach?

The iterative DFS with a stack offers a non-recursive take—O(n) time, O(h) space—using a stack to mimic the recursion. It’s useful if you prefer iteration or need to avoid stack overflow risks in deep trees. It’s like exploring the tree with a checklist, ticking off nodes as you go—methodical and explicit!

How It Works

Here’s the plan:

• Step 1: Use a stack with (node, state) pairs:
• State 0: Pre-visit (process children).
• State 1: Post-visit (compute path).
• Step 2: Track max sum and single-path gains per node.
• Step 3: Iterate until stack is empty.

Step-by-Step Example

Example: root = [1, 2, 3]

• Initialize: max_sum = -inf, stack = [(1, 0)], gains = {}.
• (1, 0):
• Push (3, 0), (2, 0).
• Stack = [(1, 0), (3, 0), (2, 0)].
• (2, 0):
• No children, pop, push (2, 1).
• Stack = [(1, 0), (3, 0), (2, 1)].
• (2, 1):
• Gain = 2, max_sum = max(-inf, 2) = 2.
• gains[2] = 2.
• (3, 0):
• No children, push (3, 1).
• (3, 1):
• Gain = 3, max_sum = max(2, 3) = 3.
• gains[3] = 3.
• (1, 0):
• Pop, push (1, 1).
• (1, 1):
• Left = 2, Right = 3.
• Path = 1 + 2 + 3 = 6.
• max_sum = max(3, 6) = 6.
• Result: 6.

Code for Iterative Approach

Copy codeclass Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        max_sum = float('-inf')
        stack = [(root, 0)]  # (node, state)
        gains = {}  # Node -> max single-path gain

        while stack:
            node, state = stack.pop()
            if state == 0:  # Pre-visit
                stack.append((node, 1))
                if node.right:
                    stack.append((node.right, 0))
                if node.left:
                    stack.append((node.left, 0))
            else:  # Post-visit
                left_gain = gains.get(node.left, 0) if node.left else 0
                right_gain = gains.get(node.right, 0) if node.right else 0
                left_gain = max(left_gain, 0)
                right_gain = max(right_gain, 0)
                current_path = node.val + left_gain + right_gain
                max_sum = max(max_sum, current_path)
                gains[node] = node.val + max(left_gain, right_gain)

        return max_sum

• Line 4-5: Handle empty tree.
• Line 7-9: Initialize max, stack, and gains.
• Line 11-25: Stack loop:
• Line 13-18: Pre-visit, push children.
• Line 20-25: Post-visit, compute path and gain.
• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(h)—stack size.

It’s a stack-driven pathfinder!

Comparing the Two Solutions

• Recursive DFS (Best):
• Pros: O(n) time, O(h) space, concise and natural.
• Cons: Relies on recursion stack.
• Iterative DFS (Alternative):
• Pros: O(n) time, O(h) space, avoids recursion.
• Cons: More complex, explicit state management.

Recursive wins for simplicity.

Additional Examples and Edge Cases

• [1]: 1.
• [-2, 6]: 6.
• [1, -2, -3]: 1.

Both handle these perfectly.

Complexity Breakdown

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

Recursive’s elegance shines.

Key Takeaways

• Recursive: DFS with global max!
• Iterative: Stack mimics recursion!
• Paths: Consider all directions.
• Python Tip: Recursion simplifies—see [Python Basics](/python/basics).

Final Thoughts: Sum the Tree

LeetCode 124: Binary Tree Maximum Path Sum in Python is a tree-summing adventure. The recursive DFS uncovers the max path with grace, while iterative DFS offers a hands-on alternative. Want more tree challenges? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 543: Diameter of Binary Tree. Ready to find your path? Head to Solve LeetCode 124 on LeetCode and claim that sum today!