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 two sorted arrays and need to find the median of their combined elements efficiently without fully merging them. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge both arrays completely and then find the median from the merged array.

B. Use binary search to partition the smaller array and find the correct partition in the other array.

C. Use a two-pointer approach to partially merge elements until the median position is reached.

D. Apply dynamic programming to store medians of subarrays and combine results.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the median of two sorted arrays without fully merging them to achieve better than O(m+n) time.

2. Step 2: Identify the optimal approach

   Binary search on the smaller array to find a partition that balances elements on both sides guarantees O(log(min(m,n))) time, which is optimal.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on partition is the known optimal solution [OK]

Hint: Optimal median uses binary search on smaller array [OK]

Common Mistakes:

• Assuming full merge is necessary
• Using two pointers without binary search
• Confusing DP with median finding

2. Given the following code snippet implementing the two-pointer approach for trapping rain water, what is the value of the variable water after the first iteration of the while loop when the input is [2, 0, 2]?

easy

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: First iteration of while loop

   height[left]=2, height[right]=2, since height[left] is not less than height[right], else branch runs. height[right]=2 ≥ right_max=0, so right_max=2, right decrements to 1, water remains 0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Water not added on first iteration because max updated [OK]

Hint: Water added only when current height < max height on that side [OK]

Common Mistakes:

• Adding water before max height is updated
• Confusing left and right pointer conditions
• Off-by-one errors in pointer movement

3. The following code attempts to implement the optimal DP solution for the Best Time to Buy Sell IV problem. Which line contains a subtle bug that can cause incorrect results for large k?

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]
    curr_dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        for t in range(1, k + 1):
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])
        next_dp, curr_dp = curr_dp, next_dp
    return next_dp[k][0]

medium

A. Line 3: The condition should be k >= n // 2 instead of k > n // 2

B. Line 10: Using next_dp[t][1] instead of next_dp[t-1][1] in curr_dp[t][0] update

C. Line 13: Swapping next_dp and curr_dp incorrectly

D. Line 7: Summing max(0, prices[i] - prices[i - 1]) without checking if prices is empty

Solution

1. Step 1: Analyze the unlimited transactions condition

   The code uses if k >= n // 2 to shortcut to unlimited transactions logic. This condition correctly covers the case when k equals half the number of days.

2. Step 2: Understand impact of the bug

   Using k > n // 2 would miss the case when k == n // 2, causing inefficient DP execution or incorrect results. The corrected code uses k >= n // 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct condition is k >= n // 2 to handle unlimited transactions case [OK]

Hint: Check boundary conditions for unlimited transactions case [OK]

Common Mistakes:

• Using > instead of >= in unlimited transactions check
• Mixing holding and not holding states in DP updates
• Incorrect dp array swapping

4. What is the time complexity of the optimal solution for Word Search II that uses backtracking with a Trie and in-place board modification, assuming the board size is NxM, the number of words is W, and the maximum length of a word is L?

medium

A. O(W * N * M * 4^L) because each word is searched independently

B. O(W * L) for building Trie plus O(N * M * 4^L) for backtracking

C. O(N * M * L * W) because Trie traversal multiplies word length and count

D. O(N * M * 4^L) due to backtracking pruning with Trie prefix checks

Solution

1. Step 1: Identify Trie construction cost

   Building the Trie takes O(W * L) time, inserting each word character by character.

2. Step 2: Analyze backtracking complexity

   Backtracking explores up to 4^L paths from each cell, so O(N * M * 4^L) dominates search time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie build plus backtracking combined yields O(W*L + N*M*4^L) [OK]

Hint: Trie build separate from backtracking cost [OK]

Common Mistakes:

• Confusing independent word search with Trie pruning
• Ignoring Trie build cost
• Multiplying all parameters incorrectly

5. Suppose the problem is modified so that the same letter cell on the board can be used multiple times within the same word search path (i.e., reuse of cells is allowed). Which modification to the optimal backtracking with Trie approach correctly handles this variant without causing infinite loops?

hard

A. Use a separate visited set to track cells per path and allow revisiting after backtracking

B. Remove the in-place marking of visited cells and rely solely on Trie pruning

C. Keep the in-place marking but reset visited cells only after exploring all neighbors

D. Modify the Trie to store counts of allowed cell reuse and decrement on each visit

Solution

1. Step 1: Understand reuse impact on visited marking

   Allowing reuse means cells can be revisited, so marking cells as visited must be carefully managed to avoid infinite loops.

2. Step 2: Identify correct marking strategy

   Using a separate visited set per path allows revisiting cells after backtracking, preventing infinite loops while supporting reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Separate visited set per path safely handles cell reuse [OK]

Hint: Track visited cells per path to allow safe reuse [OK]

Common Mistakes:

• Removing marking causes infinite loops
• Using global visited set without reset
• Modifying Trie for cell reuse incorrectly