Binary Tree Maximum Path Sum

📋

Problem

Imagine you are analyzing a network of connected nodes representing a power grid, and you want to find the path that yields the maximum total power output, even if it passes through the central hub and branches out.

Given a non-empty binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

The number of nodes in the tree is in the range [1, 10^5].-10^4 <= Node.val <= 10^4

Edge cases: Single node tree → output is the node's valueAll nodes have negative values → output is the maximum single node valueTree with only left children → path is the sum of all nodes

</>

IDE

def maxPathSum(root: TreeNode) -> int:public int maxPathSum(TreeNode root)int maxPathSum(TreeNode* root)function maxPathSum(root)

def maxPathSum(root):
    # Write your solution here
    pass

class Solution {
    public int maxPathSum(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxPathSum(TreeNode* root) {
    // Write your solution here
    return 0;
}

function maxPathSum(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for empty or negative-only subtrees instead of node.val; ignoring max_sum update for negative nodes.✅ Update max_sum with node.val even if gains are negative; return max(node.val, node.val + max(left_gain, right_gain, 0)).

Wrong: Sum of only one subtree sideGreedy approach picking max gain from only left or right subtree, ignoring paths through node connecting both sides.✅ Update max_sum with node.val + left_gain + right_gain, not just max of one side.

Wrong: Sum including negative subtree gainsAdding negative left or right subtree sums to path sum, reducing max sum.✅ Use max(left_gain, 0) and max(right_gain, 0) to exclude negative contributions.

Wrong: TLE or timeoutUsing exponential or repeated subtree computations without memoization or global tracking.✅ Use O(n) postorder traversal with global max_sum tracking to avoid recomputation.

✓

Test Cases

Focus on handling base cases like single nodes and negative values correctly.

Think about paths that pass through nodes connecting left and right subtrees, not just one side.

Optimize your solution to run in linear time using postorder traversal and global tracking.

t1_01basic

Input{"root":[1,2,3]}

Expected6

⏱ Performance - must finish in 2000ms

The path with maximum sum is 2 -> 1 -> 3, which sums to 6.

💡 Consider all paths that can pass through each node.

💡 Use postorder traversal to compute max gain from left and right subtrees.

💡 Track max sum globally by comparing node.val + left_gain + right_gain.

Why it failed: Incorrect max sum output; likely missed combining left and right subtree gains at node. Fix by updating max_sum with node.val + left_gain + right_gain during recursion.

✓ Correctly computes max path sum including paths through root and subtrees.

t1_02basic

Input{"root":[-10,9,20,null,null,15,7]}

Expected35

⏱ Performance - must finish in 2000ms

The max path is 15 -> 20 -> 7 with sum 42 is incorrect; correct max path is 15 -> 20 -> 7 with sum 42 but path must be parent-child connections. The actual max path sum is 15 + 20 + 7 = 42, but the path 9 alone is 9, so max path sum is 42. However, the path 15->20->7 is valid and sums to 42. Rechecking: 15 + 20 + 7 = 42. The original expected was 42, which is correct. But the problem states path must be parent-child connections. The path 15->20->7 is valid. So expected 42 is correct. Re-examining brute force: The path 15->20->7 sums to 42. So original expected 42 is correct. So no change needed. Correction: The original expected 42 is correct. So revert to 42.

💡 Check paths that include both left and right children of a node.

💡 Ignore negative gains by taking max with 0 for left and right gains.

💡 Update global max_sum with node.val + left_gain + right_gain.

Why it failed: Output less than 42; likely failed to ignore negative subtree sums or update global max_sum correctly. Fix by using max(left_gain, 0) and max(right_gain, 0) and updating max_sum accordingly.

✓ Handles negative values and updates max sum correctly.

t2_01edge

Input{"root":[5]}

Expected5

⏱ Performance - must finish in 2000ms

Single node tree; max path sum is the node's value itself.

💡 Consider base case when node has no children.

💡 Return node.val directly when no left or right subtree.

💡 Global max_sum should be updated with node.val even if no children.

Why it failed: Fails single node case; likely returns 0 or ignores node.val. Fix by ensuring max_gain returns node.val and updates max_sum for leaf nodes.

✓ Correctly handles single node trees.

t2_02edge

Input{"root":[-3,-2,-1]}

Expected-1

⏱ Performance - must finish in 2000ms

All nodes negative; max path sum is the maximum single node value -1.

💡 Negative values can reduce path sums; consider ignoring negative gains.

💡 Use max(left_gain, 0) and max(right_gain, 0) to avoid negative contributions.

💡 Global max_sum must track max node value even if all negative.

Why it failed: Returns sum of all negatives or 0; fails to handle all negative values correctly. Fix by updating max_sum with node.val even if gains are negative.

✓ Handles all negative values by selecting max single node.

t2_03edge

Input{"root":[1,2,null,3,null,4,null]}

Expected10

⏱ Performance - must finish in 2000ms

Tree with only left children; max path sum is sum of all nodes: 1+2+3+4=10.

💡 Check paths that extend down one side only.

💡 Postorder traversal accumulates max gain from left subtree.

💡 Global max_sum updates with sums along the chain.

Why it failed: Fails to accumulate left-only path sums; likely ignores one child or resets sum. Fix by correctly returning node.val + max(left_gain, right_gain) and updating max_sum.

✓ Correctly sums paths down left-only chains.

t3_01corner

Input{"root":[1,2,3,4,5,6,7]}

Expected18

⏱ Performance - must finish in 2000ms

Balanced tree; max path is 4 -> 2 -> 1 -> 3 -> 7 = 18.

💡 Greedy approach picking only one subtree may fail here.

💡 Must consider paths passing through node connecting left and right children.

💡 Update max_sum with node.val + left_gain + right_gain, not just max of one side.

Why it failed: Greedy approach returns 16 or less by choosing only one subtree path. Fix by considering sum of both left and right gains plus node.val for max_sum update.

✓ Correctly handles paths passing through nodes connecting two subtrees.

t3_02corner

Input{"root":[10,2,10,null,null,-20,-1]}

Expected22

⏱ Performance - must finish in 2000ms

Path 2 -> 10 -> 10 yields max sum 22; tests ignoring negative subtree sums.

💡 Avoid adding negative subtree sums to path.

💡 Use max(left_gain, 0) and max(right_gain, 0) to exclude negative paths.

💡 Update max_sum with node.val + left_gain + right_gain only if gains positive.

Why it failed: Includes negative subtree sums reducing max sum. Fix by taking max with 0 for left and right gains before adding.

✓ Excludes negative subtree sums correctly.

t3_03corner

Input{"root":[5,4,8,11,null,13,4,7,2,null,null,null,1]}

Expected48

⏱ Performance - must finish in 2000ms

Complex tree; max path sum includes multiple nodes and branches.

💡 Beware off-by-one errors in recursion or subtree gain calculations.

💡 Ensure recursive calls correctly return max gain for one side only.

💡 Update global max_sum with node.val + left_gain + right_gain at each node.

Why it failed: Off-by-one or incorrect subtree gain calculation leads to wrong max sum. Fix recursion to return node.val + max(left_gain, right_gain) and update max_sum properly.

✓ Handles complex trees with correct recursion and max sum updates.

t4_01performance

Input{"root":[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced binary tree with 127 nodes (complete tree of height 6); must complete in O(n) time within 2s.

💡 Use O(n) postorder traversal to compute max gains.

💡 Avoid recomputation by caching subtree results.

💡 Global tracking of max sum avoids repeated scans.

Why it failed: TLE due to exponential or repeated subtree computations. Fix by using O(n) postorder traversal with memoization or global tracking.

✓ Algorithm runs in O(n) time confirming efficient traversal.

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 an undirected graph with n nodes. The task is to find the shortest path length that visits every node at least once. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A bottom-up dynamic programming approach using bitmasking to represent visited nodes and states.

B. A depth-first search (DFS) that explores all permutations of node visits without memoization.

C. A simple breadth-first search (BFS) without tracking visited subsets of nodes.

D. A greedy algorithm that always moves to the nearest unvisited node until all nodes are visited.

Solution

1. Step 1: Understand the problem constraints

   The problem requires visiting all nodes with the shortest path, which is a variant of the Traveling Salesman Problem (TSP) on a graph.

2. Step 2: Identify the suitable algorithmic pattern

   Greedy or simple BFS/DFS without tracking visited subsets cannot guarantee optimality or efficiency. Bitmask DP efficiently encodes visited nodes and uses state transitions to find the shortest path.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask DP is the classic approach for shortest path visiting all nodes [OK]

Hint: Bitmask DP tracks visited subsets optimally [OK]

Common Mistakes:

• Assuming greedy is optimal
• Ignoring visited subsets in BFS
• Trying DFS without memoization

3. What is the time complexity of the optimized Fenwick Tree based algorithm for counting the number of longest increasing subsequences in an array of length n with values bounded by W (maximum distinct values)?

medium

A. O(n log n) because sorting the array dominates the complexity

B. O(n²) because each update and query can take O(n) in worst case

C. O(n log W) because each Fenwick tree update and query takes O(log W) and we do n such operations

D. O(n) because Fenwick tree operations are constant time

Solution

1. Step 1: Identify Fenwick tree operations cost

   Fenwick tree update and query each take O(log W), where W is the size of the Fenwick tree (number of distinct values).

2. Step 2: Count total operations

   We perform n updates and n queries, so total time is O(n log W). Sorting takes O(n log n), but W ≤ n, so O(n log W) dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Fenwick tree operations are logarithmic in size, repeated n times [OK]

Hint: Fenwick tree operations cost O(log W), not O(n) [OK]

Common Mistakes:

• Assuming Fenwick updates are O(n)
• Confusing n and W in complexity
• Ignoring sorting cost

4. The following code attempts to solve the Russian Doll Envelopes problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes by width ascending and height ascending

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing element in lis at found index

Solution

1. Step 1: Examine sorting order

   Sorting by width ascending and height ascending causes envelopes with same width but increasing height to be counted incorrectly in LIS.

2. Step 2: Understand LIS requirement

   Heights must be sorted descending for equal widths to avoid counting invalid envelopes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order bug leads to wrong LIS and incorrect nesting count [OK]

Hint: Sort height descending for equal widths to avoid LIS errors [OK]

Common Mistakes:

• Sorting both dimensions ascending instead of height descending
• Misusing bisect functions
• Incorrectly extracting heights

5. Suppose the problem is modified so that you can revisit cells multiple times (cycles allowed) and the path must be strictly increasing. Which approach correctly handles this variant without infinite loops?

hard

A. Use DFS with memoization and cycle detection to avoid infinite loops

B. Use topological sort based DP after detecting and removing cycles

C. Use BFS ignoring value order to find longest path

D. Use DFS without memoization to explore all paths

Solution

1. Step 1: Understand cycle implications

   Allowing revisits with strict increasing values can create cycles if not carefully handled, risking infinite loops.

2. Step 2: Identify safe approach

   DFS with memoization plus cycle detection prevents infinite recursion and correctly computes longest paths even with cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization + cycle detection ensures correctness and termination [OK]

Hint: Cycle detection needed when revisits allowed [OK]

Common Mistakes:

• Using naive DFS causing infinite loops
• Ignoring cycles in topological sort
• Using BFS without value order