Bird
Raised Fist0
Interview Prepchallenge-problemshardFacebookAmazonGoogleMicrosoft

Binary Tree Maximum Path Sum

Choose your preparation mode4 modes available
▶
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.
📊
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.
Step 1/14
·Active fill★Answer cell
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/5)
1. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)
easy
A. True
B. False
C. Raises an exception due to null pointer
D. Returns True only if the root value equals targetSum

Solution

  1. Step 1: Trace the path sums

    Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.
  2. Step 2: Confirm code logic

    The DFS returns True as soon as it finds the matching path sum at a leaf node.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Path 5↔4↔11↔2 sums to 22, so return True [OK]
Hint: Check all root-to-leaf paths, not just partial sums [OK]
Common Mistakes:
  • Stopping at non-leaf nodes
  • Ignoring leaf node condition
2. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?
easy
A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.
B. Perform a level-order traversal and compare nodes at each level from left to right.
C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.
D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

  1. Step 1: Understand the problem requires mirrored subtree comparison

    The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.
  2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

    The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Mirrored recursive DFS matches problem requirements [OK]
Hint: Symmetry requires mirrored subtree comparison [OK]
Common Mistakes:
  • Assuming preorder traversal palindrome check works
  • Using level-order traversal without mirrored comparison
  • Trying brute force subtree permutations
3. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?
medium
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(n h) where h is tree height

Solution

  1. Step 1: Analyze height computation calls

    Height is computed recursively for each node, and each height call traverses subtree nodes.
  2. Step 2: Calculate total calls

    For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Repeated height calls cause quadratic time [OK]
Hint: Repeated height calls cause O(n²) time [OK]
Common Mistakes:
  • Assuming height calls are O(1) leading to O(n) time
  • Confusing height with depth or tree height h
  • Thinking O(n log n) due to balanced tree assumption
4. Consider the following buggy code for inverting a binary tree. Which line contains the subtle bug that causes incorrect inversion?
medium
A. Line 3: Swapping children before recursive calls
B. Line 5: Recursive call on right child
C. Line 4: Recursive call on left child
D. Line 2: Missing check for empty tree

Solution

  1. Step 1: Analyze order of operations

    The code swaps children before recursively inverting subtrees, which means subtrees are swapped but not inverted themselves.
  2. Step 2: Identify why swapping before recursion is incorrect

    Swapping first causes recursion to invert the wrong subtrees, leading to partial or incorrect inversion.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Swapping must happen after recursive calls to invert subtrees correctly [OK]
Hint: Swap after recursion, not before, to invert subtrees properly [OK]
Common Mistakes:
  • Swapping children before recursion
  • Ignoring null root checks
  • Confusing left and right subtree recursion order
5. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?
hard
A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.
B. Use the brute force approach checking all paths from every node without prefix sums.
C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.
D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

  1. Step 1: Understand path direction relaxation

    Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.
  2. Step 2: Model tree as undirected graph and run DFS from every node

    To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Undirected DFS from every node with prefix sums counts all connected paths [OK]
Hint: Undirected graph DFS needed for arbitrary path directions [OK]
Common Mistakes:
  • Trying to reuse one-directional prefix sum DFS without modification
  • Assuming running DFS twice covers all paths
  • Trying to store both directions in one prefix sum map
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard