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. Given the following Morris inorder traversal code, what is the final output list after running inorderTraversal on this tree?

Tree structure:
2
/ \ 1 3

from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)  # visit node
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                predecessor.right = None  # remove thread
                result.append(current.val)  # visit node
                current = current.right
    return result

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [2, 1, 3]

D. [3, 2, 1]

Solution

1. Step 1: Trace traversal starting at root=2

   Current=2 has left child 1, find predecessor in left subtree: node 1 (no right child). Create thread from 1.right to 2, move current to 1.

2. Step 2: Visit node 1 (no left child), append 1, move current to 1.right which points to 2 (thread).

   Remove thread, append 2, move current to 2.right=3. Node 3 has no left child, append 3, move current to null.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder traversal of tree 1,2,3 is [1,2,3] [OK]

Hint: Inorder traversal visits left, root, right [OK]

Common Mistakes:

• Appending before removing thread
• Visiting root before left subtree
• Confusing preorder with inorder output

2. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

    1
   / \
  2   3

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result

easy

A. [2, 1, 3]

B. [1, 2, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Trace first iteration with current=1

   Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.

2. Step 2: Trace second iteration with current=2

   Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).

3. Step 3: Detect thread at 2.right=1

   Since predecessor.right == current, reset 2.right=None, move current=1.right=3.

4. Step 4: Trace current=3

   Node 3 has no left child, append 3, move current=3.right=None, loop ends.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Output matches preorder traversal [1,2,3] [OK]

Hint: Morris preorder appends root before left subtree [OK]

Common Mistakes:

• Appending nodes in wrong order
• Not resetting threaded links
• Confusing left and right child traversal

3. Consider this modified code snippet for the Binary Tree Cameras problem. Which line contains the subtle bug that causes incorrect camera placement?

medium

A. Line returning COVERED_NO_CAM after placing a camera instead of HAS_CAM

B. Line returning NOT_COVERED at the end of dfs

C. Line checking if dfs(root) == NOT_COVERED after traversal

D. Line returning COVERED_NO_CAM when node is null

Solution

1. Step 1: Identify camera placement logic

   When a child is NOT_COVERED, a camera must be placed at current node and dfs must return HAS_CAM to indicate camera presence.

2. Step 2: Locate incorrect return

   The code returns COVERED_NO_CAM after placing a camera, which falsely signals no camera here, causing parents to misinterpret coverage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning HAS_CAM is essential after placing a camera [OK]

Hint: Return HAS_CAM after placing camera to signal coverage [OK]

Common Mistakes:

• Returning COVERED_NO_CAM instead of HAS_CAM after camera placement
• Forgetting to add camera if root uncovered
• Mixing coverage states in conditions

4. What is the time complexity of the iterative postorder traversal using one stack and a pointer on a binary tree with n nodes?

medium

A. O(n log n) due to repeated stack operations

B. O(n) but with O(h) auxiliary space where h is tree height

C. O(n^2) because of nested while loops

D. O(n) because each node is visited and processed once

Solution

1. Step 1: Analyze node visits

   Each node is pushed and popped exactly once, so operations proportional to n.

2. Step 2: Confirm no nested repeated work

   Inner loops traverse down left children, but total iterations over all nodes sum to n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear time complexity matches traversal of all nodes once [OK]

Hint: Each node processed once -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops multiply to n^2
• Confusing auxiliary space with time

5. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?

hard

A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.

B. The optimal binary search approach on the last level still applies with minor modifications.

C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).

D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.

Solution

1. Step 1: Understand the problem change

   The tree is no longer complete, so properties used by optimal methods do not hold.

2. Step 2: Identify correct counting method

   Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal methods rely on completeness, which is lost here [OK]

Hint: Without completeness, must traverse all nodes [OK]

Common Mistakes:

• Trying to apply binary search on last level
• Assuming height checks still reduce complexity