Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonFacebookGoogle

Path Sum III (Any Path)

Choose your preparation mode4 modes available
</>
IDE
def pathSum(root: Optional[TreeNode], targetSum: int) -> int:public int pathSum(TreeNode root, int targetSum)int pathSum(TreeNode* root, int targetSum)function pathSum(root, targetSum)
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.

t2_01edge
Input{"root":null,"targetSum":0}
Expected0

Empty tree has no paths, so result is 0.

t2_02edge
Input{"root":[5],"targetSum":5}
Expected1

Single node equals targetSum, so one valid path.

t2_03edge
Input{"root":[5],"targetSum":10}
Expected0

Single node does not equal targetSum, so no valid paths.

t2_04edge
Input{"root":[0,0,0,0,0,0,0],"targetSum":0}
Expected28

All nodes zero and targetSum zero; count all downward paths. Total paths = 28.

t3_01corner
Input{"root":[1,2,3],"targetSum":5}
Expected0

No downward path sums to 5; tests greedy approach that picks largest child only.

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

Tests confusion between 0/1 and unbounded path counting; paths are linear down right children.

t3_03corner
Input{"root":[1,-1,1,-1,null,null,1],"targetSum":0}
Expected4

Tests handling of negative values and zero targetSum; multiple paths sum to zero.

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],"targetSum":3}
⏱ Performance - must finish in 2000ms

Large skewed tree with n=100 nodes, O(n) solution must complete in 2s.

Practice

(1/5)
1. You are given a binary tree and two nodes within it. You need to find the node that is the deepest common ancestor of both nodes. Which approach guarantees an optimal solution in terms of time and space complexity?
easy
A. Use a brute force approach by finding paths from root to each node and then comparing the paths.
B. Build a parent pointer map for all nodes, then use ancestor sets to find the lowest common ancestor.
C. Apply a greedy algorithm that picks the first common node found during a preorder traversal.
D. Use dynamic programming to store results of subtrees and combine them to find the ancestor.

Solution

  1. Step 1: Understand problem constraints

    The problem requires finding the lowest common ancestor efficiently, ideally in O(n) time and O(n) space.
  2. Step 2: Evaluate approaches

    Brute force (A) is correct but less optimal. Greedy (C) fails because it may pick incorrect ancestors. DP (D) is not applicable here. Building parent pointers and using ancestor sets (B) provides an optimal and clean solution.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Parent pointer + ancestor set approach is standard optimal solution [OK]
Hint: Parent pointers + ancestor sets yield optimal LCA solution [OK]
Common Mistakes:
  • Assuming greedy traversal finds correct LCA
  • Using DP where not applicable
  • Brute force is optimal
2. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?
medium
A. Line 1: Missing check for empty root before traversal
B. Line 7: Incorrectly pushing node.left without null check
C. Line 12: Comparing last_visited with peek.right incorrectly
D. Line 16: Using abs difference without considering null children

Solution

  1. Step 1: Identify handling of empty tree

    The code does not check if root is None before starting traversal, which can cause errors or incorrect results.
  2. Step 2: Verify other lines

    Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing early return for empty root causes bug [OK]
Hint: Always check for empty root before traversal [OK]
Common Mistakes:
  • Forgetting to handle empty tree as balanced
  • Incorrectly comparing last_visited causing infinite loops
  • Not defaulting heights for null children
3. 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
4. What is the time complexity of the optimized iterative approach using a stack and a hash map to build a binary tree from preorder and inorder traversals of length n?
medium
A. O(n^2) due to nested loops scanning preorder and inorder arrays
B. O(n log n) due to hash map lookups for inorder indices
C. O(n) because each node is pushed and popped at most once from the stack
D. O(n) but with O(n^2) auxiliary space for recursion stack

Solution

  1. Step 1: Analyze main loops

    The algorithm iterates preorder once, pushing and popping nodes from stack at most once each.
  2. Step 2: Consider hash map lookups

    Hash map lookups for inorder indices are O(1) each, so no extra log factor.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Each node processed once with O(1) operations [OK]
Hint: Each node pushed and popped once; hash map lookups O(1) [OK]
Common Mistakes:
  • Assuming nested loops cause O(n^2)
  • Confusing hash map lookup cost
  • Counting recursion stack space in iterative approach
5. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total
medium
A. Line with 'if not node:' return statement
B. Line adding current_number to self.total
C. Line checking if node is leaf
D. Line calling dfs on node.right

Solution

  1. Step 1: Understand when sums should be added

    Sum should only include complete root-to-leaf numbers, so addition must happen only at leaf nodes.
  2. Step 2: Identify incorrect addition

    Adding current_number at every node (including non-leaf) causes partial numbers to be summed, inflating total incorrectly.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum only at leaves fixes the bug [OK]
Hint: Add to total only at leaf nodes [OK]
Common Mistakes:
  • Adding partial path sums at non-leaf nodes
  • Not resetting total between calls
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