Binary Tree Maximum Path Sum

▶

Steps

setup

Start at Root Node

We begin the recursion at the root node with value 1. The global max_sum is initialized to negative infinity.

💡 Initializing max_sum to -inf ensures any path sum will update it.

Line:

def maxPathSum(root):
    max_sum = float('-inf')
    def helper(node):

💡 The algorithm starts with the root and prepares to explore all paths.

traverse

Recurse Left Child of Root

The recursion moves to the left child node with value 2 to compute its max gain.

💡 We must find the max gain from the left subtree before processing the root fully.

Line:

left = max(helper(node.left), 0)

💡 Recursion explores left subtree first to gather information for the root's max path calculation.

traverse

Recurse Left Child of Node 2 (None)

Node 2's left child is null, so recursion returns 0 as max gain from this path.

💡 Null children contribute 0 to path sums, preventing negative impact.

Line:

if not node:
    return 0

💡 Base case of recursion returns 0 for null nodes.

traverse

Recurse Right Child of Node 2 (None)

Node 2's right child is also null, so recursion returns 0 as max gain.

💡 Both children of leaf nodes return 0, so leaf node's gain is its own value.

Line:

if not node:
    return 0

💡 Leaf nodes have no children, so gains from children are zero.

compare

Calculate Max Gain at Node 2

At node 2, left and right gains are both 0. The max path through node 2 is 2 + 0 + 0 = 2. Update max_sum to 2.

💡 We update global max_sum if current path sum is better.

Line:

left = max(helper(node.left), 0)
right = max(helper(node.right), 0)
max_sum = max(max_sum, node.val + left + right)

💡 Leaf node's value can be a candidate for max path sum.

traverse

Return Max Gain from Node 2 to Parent

Return max gain from node 2 to its parent: 2 + max(0, 0) = 2.

💡 This gain will be used by the root node to compute its max path sum.

Line:

return node.val + max(left, right)

💡 The recursion returns the best gain path upwards.

traverse

Recurse Right Child of Root

Now recursion moves to the right child node with value 3 to compute its max gain.

💡 We explore the right subtree to gather gains for the root node.

Line:

right = max(helper(node.right), 0)

💡 Right subtree is explored after left subtree.

traverse

Recurse Left Child of Node 3 (None)

Node 3's left child is null, so recursion returns 0 as max gain.

💡 Null children return 0 to avoid negative impact on path sums.

Line:

if not node:
    return 0

💡 Base case applies to right subtree leaves as well.

traverse

Recurse Right Child of Node 3 (None)

Node 3's right child is null, so recursion returns 0 as max gain.

💡 Both children of node 3 return 0, so node 3's gain is its own value.

Line:

if not node:
    return 0

💡 Leaf node 3 contributes its own value as max gain.

compare

Calculate Max Gain at Node 3

At node 3, left and right gains are 0. Max path through node 3 is 3 + 0 + 0 = 3. Update max_sum to max(2,3) = 3.

💡 Global max_sum updates if current path sum is better.

Line:

max_sum = max(max_sum, node.val + left + right)

💡 Max path sum can come from right subtree leaf nodes.

traverse

Return Max Gain from Node 3 to Parent

Return max gain from node 3 to root: 3 + max(0, 0) = 3.

💡 This gain will be used by the root node to compute its max path sum.

Line:

return node.val + max(left, right)

💡 Recursion returns best gain path upwards.

compare

Calculate Max Gain at Root Node

At root node 1, left gain is 2, right gain is 3. Max path through root is 1 + 2 + 3 = 6. Update max_sum to max(3,6) = 6.

💡 Root node combines left and right gains to find max path sum including both sides.

Line:

max_sum = max(max_sum, node.val + left + right)

💡 Max path sum can pass through root connecting left and right subtrees.

traverse

Return Max Gain from Root to Parent (None)

Return max gain from root to parent (none): 1 + max(2, 3) = 4. This is the max gain root can contribute upwards.

💡 Return value is used if root had a parent; here it ends recursion.

Line:

return node.val + max(left, right)

💡 Max gain returned is the best single path from root down.

reconstruct

Final Result Returned

Recursion completes and max_sum holds the maximum path sum 6, which is returned as the final answer.

💡 The global max_sum is the answer to the problem.

Line:

helper(root)
return max_sum

💡 The algorithm returns the maximum path sum found in the entire tree.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    max_sum = float('-inf')  # STEP 1

    def helper(node):
        nonlocal max_sum
        if not node:  # STEP 3,4,8,9
            return 0
        left = max(helper(node.left), 0)  # STEP 2,7
        right = max(helper(node.right), 0)  # STEP 7
        max_sum = max(max_sum, node.val + left + right)  # STEP 5,10,12
        return node.val + max(left, right)  # STEP 6,11,13

    helper(root)  # STEP 1
    return max_sum  # STEP 14

📊

Binary Tree Maximum Path Sum - Watch the Algorithm Execute, Step by Step

Watching the recursion unfold and how the algorithm chooses paths helps you understand the problem's complexity and the importance of ignoring negative gains.

traverse

node

1

0

2

1

3

2

Result: "-inf"

traverse

1

0

node

2

1

3

2

Result: "-inf"

traverse

1

0

2

1

3

2

Result: "-inf"

traverse

1

0

2

1

3

2

Result: "-inf"

compare

1

0

node

2

1

3

2

Result: 2

move_right

1

0

node

2

1

3

2

Result: 2

traverse

1

0

2

1

node

3

2

Result: 2

traverse

1

0

2

1

3

2

Result: 2

traverse

1

0

2

1

3

2

Result: 2

compare

1

0

2

1

node

3

2

Result: 3

move_left

1

0

2

1

node

3

2

Result: 3

compare

node

1

0

2

1

3

2

Result: 6

move_left

node

1

0

2

1

3

2

Result: 6

record

1

0

2

1

3

2

Result: 6

Key Takeaways

✓ The maximum path sum can include both left and right children of a node, not just a single path downwards.

This is hard to see from code alone because the return value only represents one path, but the global max_sum tracks combined paths.

✓ Negative gains from children are ignored by taking max with 0, ensuring paths only add positive contributions.

This prevents paths with negative sums from reducing the overall maximum, a subtle but crucial insight.

✓ The recursion explores the entire tree bottom-up, computing gains from leaves up to the root, updating max_sum at each node.

Seeing the recursion order and how gains propagate clarifies the algorithm's flow better than reading code.

Practice

1. You are given a binary tree and a target sum. The task is to find all root-to-leaf paths where the sum of the node values equals the target sum. Which algorithmic approach guarantees finding all such paths efficiently?

easy

A. Greedy traversal choosing the child with the closest value to the remaining sum

B. Depth-first search (DFS) with path tracking and backtracking to explore all root-to-leaf paths

C. Dynamic programming to store sums at each node and combine results bottom-up

D. Breadth-first search (BFS) with queue to find the shortest path matching the sum

Solution

1. Step 1: Understand problem requires all root-to-leaf paths

   Since we must find all paths, not just one, exhaustive exploration is needed.

2. Step 2: Identify DFS with path tracking and backtracking

   DFS explores each path fully, tracking the current path and sum, backtracking to explore alternatives.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS explores all paths, greedy or BFS do not guarantee all paths [OK]

Hint: All root-to-leaf paths require exhaustive DFS [OK]

Common Mistakes:

• Thinking greedy or BFS finds all paths
• Confusing DP for path enumeration

2. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?

medium

A. O(n^2) due to checking grandchildren nodes explicitly

B. O(n) but with extra O(n) space for memoization arrays

C. O(n) because each node is visited once in DFS

D. O(n log n) because of recursive calls and combining results

Solution

1. Step 1: Identify DFS traversal cost

   The algorithm visits each node exactly once in a postorder DFS traversal.

2. Step 2: Analyze operations per node

   At each node, constant time operations are done: combining left and right child results, no repeated work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal of n nodes -> O(n) time [OK]

Hint: DFS visits each node once, no repeated subproblems [OK]

Common Mistakes:

• Assuming O(n^2) due to grandchildren checks
• Confusing recursion stack space with time complexity

3. Examine the following buggy code for the Path Sum problem. Which line contains the subtle bug that causes incorrect results on some inputs?

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if curr_sum == targetSum:  # Bug here
            return True
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

medium

A. Line 3: if not node: return False

B. Line 6: if curr_sum == targetSum:

C. Line 8: return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

D. Line 5: curr_sum += node.val

Solution

1. Step 1: Understand leaf node condition

   The sum should be checked only at leaf nodes, not at every node.

2. Step 2: Identify the bug

   Line 6 checks sum at any node, causing premature True returns for partial paths.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bug causes incorrect True if partial path sum equals targetSum [OK]

Hint: Sum check must be at leaf nodes only [OK]

Common Mistakes:

• Checking sum at internal nodes
• Not handling null root

4. If the binary tree nodes can have parent pointers in addition to left and right children, which modification to the iterative one-stack postorder traversal algorithm can eliminate the need for the last_visited variable?

hard

A. Use the parent pointer to move back up after visiting a node's children, tracking traversal direction

B. Push nodes twice onto the stack to simulate postorder without tracking last visited

C. Perform a preorder traversal and reverse the output list at the end

D. Use two stacks: one for traversal and one for output, ignoring parent pointers

Solution

1. Step 1: Understand role of last_visited

   Last_visited tracks if right child was processed to avoid revisiting; parent pointers can provide traversal direction.

2. Step 2: Use parent pointer to detect traversal direction

   By moving up via parent pointer, algorithm knows if coming from left or right child, eliminating need for last_visited.

3. Step 3: Compare other options

   Options B and D ignore parent pointers; A reverses preorder but does not leverage parent pointers; C uses parent pointers effectively.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Parent pointers enable direction-aware traversal without extra state [OK]

Hint: Parent pointers track traversal direction, removing last_visited [OK]

Common Mistakes:

• Ignoring parent pointers
• Using two stacks unnecessarily
• Reversing preorder output without parent info

5. Suppose you want to extend the serialization/deserialization to support binary trees where nodes can have duplicate values and the tree can be very deep (height > 10,000). Which modification is necessary to ensure correctness and efficiency?

hard

A. Use iterative BFS serialization with null markers and iterative deserialization to avoid recursion stack overflow.

B. Use recursive DFS with memoization to handle duplicates and deep trees efficiently.

C. Switch to preorder traversal without null markers to reduce string size and recursion depth.

D. Serialize only unique node values and reconstruct tree assuming balanced shape.

Solution

1. Step 1: Identify problem with deep recursion

   Recursive DFS can cause stack overflow on very deep trees.

2. Step 2: Use iterative BFS with null markers

   Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.

3. Step 3: Avoid assumptions about uniqueness or balanced shape

   Duplicates require storing all nodes explicitly; balanced assumptions break correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Iterative BFS with null markers handles deep trees and duplicates safely [OK]

Hint: Iterative BFS avoids recursion limits and preserves structure [OK]

Common Mistakes:

• Removing null markers to save space breaks reconstruction
• Using recursion on deep trees causes stack overflow
• Assuming unique values or balanced trees