Interview Preptree-dfsmediumAmazonFacebookGoogle

Path Sum III (Any Path)

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

</>

IDE

def pathSum(root: Optional[TreeNode], targetSum: int) -> int:

def pathSum(root, targetSum):
    # Write your solution here
    pass

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

#include <vector>
using namespace std;

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

function pathSum(root, targetSum) {
    // Write your solution here
}

0/10

Common Bugs to Avoid

Wrong: 0Only counting paths starting at root, missing paths starting at other nodes.✅ Recursively check paths starting from every node or use prefix sum map to count all subpaths.

Wrong: 1Counting only single node paths or ignoring multi-node paths.✅ Use DFS to explore all downward paths and accumulate sums properly.

Wrong: crash or exceptionNo null check for empty tree input.✅ Add base case: if root is None, return 0 immediately.

Wrong: incorrect large countCounting nodes multiple times per path or allowing reuse.✅ Ensure each path is downward and nodes are used once per path; use prefix sums correctly.

Wrong: TLEUsing brute force O(n^2) approach on large input.✅ Implement prefix sum with DFS and hash map for O(n) time complexity.

✓

Test Cases

t1_01basic

Input{"root":[10,5,-3,3,2,null,11,3,-2,null,1],"targetSum":8}

Expected3

The paths that sum to 8 are: 5->3, 5->2->1, and -3->11.

t1_02basic

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

Expected4

Paths summing to -1 are: 1->-2->1->-1, -2->1->-1, -3->-2, and -1 alone.

Practice

(1/5)

1. You are given two arrays representing the preorder and inorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant subtree searches?

easy

A. Use breadth-first search to build the tree level by level from preorder and inorder arrays.

B. Use a greedy approach that picks nodes based on preorder and attaches them arbitrarily to the left or right.

C. Use dynamic programming to store subtree results and combine them for the full tree.

D. Use recursion with a hash map to quickly find root indices in inorder traversal, avoiding repeated searches.

2. Consider the following iterative DFS code for finding all root-to-leaf paths with a given sum. Given the tree below and targetSum = 7, what is the final returned list? Tree structure: 5 / \ 4 8 / / \ 11 13 4 Target sum: 7

def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if not node.left and not node.right:
            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

easy

A. []

B. [[5, 4, 11]]

C. [[5, 4]]

D. [[5, 8, 4]]

4. 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}

Path Sum III (Any Path)

Start learning this pattern below

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Trace paths and sums

Step 2: Confirm no leaf path sums to 7

Final Answer:

Quick Check:

Solution

Step 1: Understand the need for null markers

Step 2: Recognize BFS with null markers preserves structure

Final Answer:

Quick Check:

Solution

Step 1: Analyze parent map construction loop

Step 2: Identify subtle bug

Step 3: Explanation

Final Answer:

Quick Check:

Solution

Step 1: Recognize diameter depends on path length (edges), not node values.

Step 2: Confirm standard height-based diameter algorithm works unchanged.

Final Answer:

Quick Check: