Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoftFacebook

Path Sum

Choose your preparation mode4 modes available
</>
IDE
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:public boolean hasPathSum(TreeNode root, int targetSum)bool hasPathSum(TreeNode* root, int targetSum)function hasPathSum(root, targetSum)
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    # Write your solution here
    pass
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Write your solution here
        return false;
    }
}
#include <vector>
using namespace std;

bool hasPathSum(TreeNode* root, int targetSum) {
    // Write your solution here
    return false;
}
function hasPathSum(root, targetSum) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: true for input with no root-to-leaf path summing to targetSumNot checking if node is leaf before comparing sum, allowing partial paths to count.✅ Add condition to check if node.left == null and node.right == null before comparing sum to targetSum.
Wrong: false for input where path sum exists with negative valuesIncorrect sum accumulation ignoring negative values or early pruning.✅ Accumulate sums correctly including negative values; do not prune paths prematurely.
Wrong: true for input where greedy picks largest child first but no valid pathUsing greedy approach instead of exploring all paths.✅ Use full DFS traversal exploring both left and right children regardless of values.
Wrong: true for empty tree inputNot handling null root case properly.✅ Return false immediately if root is null.
Wrong: TLE on large inputExponential recursion or repeated work without pruning.✅ Implement O(n) DFS with early stopping and no repeated computations.
✓
Test Cases
t1_01basic
Input{"root":[5,4,8,11,null,13,4,7,2,null,null,null,1],"targetSum":22}
Expectedtrue

The path 5->4->11->2 sums to 22.

t1_02basic
Input{"root":[1,2,3],"targetSum":5}
Expectedfalse

No root-to-leaf path sums to 5 (paths: 1->2=3, 1->3=4).

t2_01edge
Input{"root":[],"targetSum":0}
Expectedfalse

Empty tree has no paths, so return false.

t2_02edge
Input{"root":[7],"targetSum":7}
Expectedtrue

Single node tree where node value equals targetSum returns true.

t2_03edge
Input{"root":[7],"targetSum":10}
Expectedfalse

Single node tree where node value does not equal targetSum returns false.

t2_04edge
Input{"root":[1,-2,-3,1,3,-2,null,-1],"targetSum":-1}
Expectedtrue

Path 1->-2->1->-1 sums to -1, demonstrating negative values handled correctly.

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

No root-to-leaf path sums to 10; tests greedy approach that picks largest child first.

t3_02corner
Input{"root":[1,2],"targetSum":1}
Expectedfalse

Tests confusion between root-to-leaf and root-to-any-node path sums; only leaf paths count.

t3_03corner
Input{"root":[1,2,null,3,null,4,null,5],"targetSum":15}
Expectedtrue

Deep unbalanced tree tests stack overflow or incorrect recursion termination.

t4_01performance
Input{"root":[1,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1],"right":null}
⏱ Performance - must finish in 2000ms

Deep left-skewed tree with 100000 nodes; O(n) DFS must complete within 2 seconds.

Practice

(1/5)
1. Given the following code snippet for serialization using BFS, what is the serialized string output for the binary tree below? Tree: 1 / \ 2 3 / \ 4 null
from collections import deque

def serialize(root):
    if not root:
        return ''
    queue = deque([root])
    vals = []
    while queue:
        node = queue.popleft()
        if node:
            vals.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            vals.append('X')
    while vals and vals[-1] == 'X':
        vals.pop()
    return ','.join(vals)
easy
A. 1,2,3,4,X,X,X
B. 1,2,3,X,X,4
C. 1,2,3,X,X,4,X,X,X
D. 1,2,3,X,X,4,X

Solution

  1. Step 1: Trace queue processing

    Start with queue=[1]. Pop 1, append '1', enqueue 2 and 3. Queue=[2,3].
  2. Step 2: Continue BFS and record values

    Pop 2, append '2', enqueue left and right (both null) -> enqueue X,X. Pop 3, append '3', enqueue 4 and null -> enqueue 4,X. Pop nulls append 'X'. Remove trailing 'X's at end.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Serialized string matches BFS with null markers trimmed correctly [OK]
Hint: Trailing 'X's are removed after BFS serialization [OK]
Common Mistakes:
  • Including trailing null markers that should be trimmed
  • Missing null markers for missing children
  • Confusing order of nodes in BFS
2. What is the space complexity of the optimal recursive approach to invert a binary tree, assuming the tree has n nodes and height h?
medium
A. O(n) because each node's children pointers are swapped individually
B. O(n) due to storing all nodes in a queue during traversal
C. O(1) because inversion is done in-place without extra data structures
D. O(h) due to recursion stack depth proportional to tree height

Solution

  1. Step 1: Identify auxiliary space usage in recursion

    The algorithm uses recursion, so the call stack depth is proportional to the height h of the tree.
  2. Step 2: Distinguish between in-place operations and recursion stack

    Swapping pointers is in-place (O(1) per node), but recursion stack space is O(h), not O(n).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Recursion stack dominates space, proportional to tree height h [OK]
Hint: Recursion stack space depends on tree height, not node count [OK]
Common Mistakes:
  • Confusing in-place operation with O(1) total space
  • Assuming queue-based BFS space applies to recursive DFS
  • Counting node swaps as extra space
3. The following code attempts to find the Lowest Common Ancestor using parent pointers. Identify the line containing the subtle bug that causes incorrect results when one node is ancestor of the other.
def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q
medium
A. Line: while p not in parent or q not in parent:
B. Line: while p:
C. Line: while q not in ancestors:
D. Line: parent = {root: None}

Solution

  1. Step 1: Analyze parent map construction loop

    The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.
  2. Step 2: Identify subtle bug

    If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.
  3. Step 3: Explanation

    The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Loop condition must ensure both nodes are in parent map to avoid errors [OK]
Hint: Parent map construction loop must fully process both nodes [OK]
Common Mistakes:
  • Assuming parent map always complete
  • Ignoring incomplete parent map causing KeyError
  • Misplacing bug in ancestor set loops
4. Examine the following buggy iterative DFS code for finding all root-to-leaf paths with a given sum. Which line contains the subtle bug that causes incorrect results?
def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if current_sum == targetSum:
            res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res
medium
A. Line appending left child to stack
B. Line initializing stack with root node and path
C. Line appending right child to stack
D. Line checking if current_sum == targetSum without verifying leaf node

Solution

  1. Step 1: Identify condition for adding path to results

    Correct code adds path only if current node is leaf and sum matches.
  2. Step 2: Locate bug

    Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Missing leaf check causes incorrect paths in results [OK]
Hint: Always check leaf node before adding path [OK]
Common Mistakes:
  • Adding path before confirming leaf node
  • Forgetting to backtrack in recursion
5. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?
hard
A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting
B. Use recursion on parent pointers to simulate traversal
C. Iteratively traverse using parent pointers and a stack to track visited nodes
D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

  1. Step 1: Understand traversal constraints

    Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.
  2. Step 2: Identify correct approach

    Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Modified iterative approach handles parent-only trees without extra space [OK]
Hint: Parent-only trees require tracking visited nodes iteratively [OK]
Common Mistakes:
  • Trying to use recursion without child pointers
  • Attempting Morris traversal on parent pointers
  • Using stack without tracking visited nodes
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