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. Consider the following code that finds the longest chain of pairs. What is the value of count after processing the input [[1,2],[2,3],[3,4]]?

easy

A. 2

B. 0

C. 1

D. 3

Solution

1. Step 1: Sort pairs by their end values

   Sorted pairs: [[1,2], [2,3], [3,4]] (already sorted)

2. Step 2: Iterate and count valid pairs

   Start with current_end = -inf, count = 0 - Pair [1,2]: 1 > -inf -> count=1, current_end=2 - Pair [2,3]: 2 > 2? No -> skip - Pair [3,4]: 3 > 2 -> count=2, current_end=4

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count increments twice for valid chains [OK]

Hint: Check strict greater than current_end [OK]

Common Mistakes:

• Counting pairs where start equals current_end
• Off-by-one errors in counting
• Misunderstanding sorting order

2. You are given a 2D grid of integers and need to find the length of the longest strictly increasing path moving only up, down, left, or right. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that always moves to the neighbor with the largest value

B. Topological sort based dynamic programming processing cells in ascending order of their values

C. Simple DFS from each cell without memoization

D. Breadth-first search layer by layer from the smallest values

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest strictly increasing path in a matrix, which can be modeled as a directed graph where edges go from smaller to larger values.

2. Step 2: Identify suitable algorithm

   Topological sort based DP processes nodes in ascending order, ensuring all dependencies are resolved before updating dp values, guaranteeing optimal substructure and avoiding recomputation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Topological sort ensures correct order for DP updates [OK]

Hint: Longest increasing path -> topological sort DP [OK]

Common Mistakes:

• Assuming greedy always works
• Using DFS without memoization causing TLE
• Using BFS layer by layer ignoring value order

3. What is the time complexity of the optimal bottom-up DFS solution for computing the diameter of a binary tree with n nodes?

medium

A. O(n) because each node is visited once in the DFS traversal

B. O(n^2) due to repeated height computations in recursion

C. O(n log n) because height computations take log n time per node

D. O(n) but with additional O(n) space for memoization arrays

Solution

1. Step 1: Identify that naive recursive approach causes repeated height computations

   In naive recursion without memoization, height computations are repeated, causing O(n^2) time complexity.

2. Step 2: Confirm that optimal bottom-up DFS avoids repeated computations

   The question asks for the optimal bottom-up DFS solution, which is O(n), but the options are designed to test understanding of naive vs optimal.

3. Step 3: Since O(n) because each node is visited once in the DFS traversal states optimal O(n), but O(n^2) due to repeated height computations in recursion states O(n^2) due to repeated computations, and question asks for optimal solution, correct answer is A.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Single DFS traversal over n nodes -> O(n) time [OK]

Hint: Single DFS traversal means linear time [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming height calls cost log n each

4. The following code attempts to implement the optimized LIS algorithm. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 3: initializing tails as empty list

B. Line 6: using bisect_left instead of bisect_right

C. Line 9: replacing tails[idx] with num + 1 instead of num

D. Line 10: returning length of tails

Solution

1. Step 1: Analyze line replacing tails element

   Replacing tails[idx] with num + 1 corrupts the tails array, which must store actual numbers from input.

2. Step 2: Understand impact

   This causes incorrect binary search behavior and wrong LIS length calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   tails must store input elements, not modified values [OK]

Hint: tails must store actual nums, not altered values [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Modifying values before storing in tails
• Misunderstanding tails purpose

5. Suppose the problem is modified so that caps can be assigned to multiple people (i.e., caps are no longer unique). Which of the following algorithmic changes correctly adapts the solution to count the number of ways to assign caps without uniqueness constraints?

hard

A. Remove bitmask tracking and use simple multiplication of counts per person

B. Keep bitmask DP but allow assigning the same cap multiple times by not checking mask bits

C. Use a DP over persons only, multiplying the number of caps each person can wear

D. Use a nested loop over persons and caps without bitmask, summing ways for each person independently

Solution

1. Step 1: Understand the uniqueness constraint removal

   Without uniqueness, caps can be reused freely, so no need to track assigned caps with bitmasks.

2. Step 2: Simplify counting approach

   Counting ways reduces to multiplying the number of caps each person can wear, as assignments are independent.

3. Step 3: Why other options fail

   Bitmask DP is unnecessary and incorrect if caps can be reused; summing independently without multiplication misses combinations.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing bitmask and multiplying counts per person matches problem relaxation [OK]

Hint: No uniqueness -> no bitmask needed, multiply counts [OK]

Common Mistakes:

• Trying to keep bitmask DP unnecessarily
• Summing instead of multiplying counts