Path Sum III (Path in Tree)

Data Structures
Hard
Google
31.9K views

Given the root of a binary tree and an integer `targetSum`, return the number of paths where the sum of the values equals `targetSum`. The path does not need to start or end at the root or a leaf. Use a HashMap for efficient path tracking.

Why Interviewers Ask This

Google interviewers ask this question to evaluate a candidate's ability to optimize brute-force tree traversals using advanced data structures. They specifically test your understanding of prefix sums and hash map usage to reduce time complexity from O(N^2) to O(N). It assesses whether you can handle non-standard path constraints where paths start and end anywhere, requiring deep insight into recursive state management.

How to Answer This Question

1. Clarify the problem scope immediately: confirm that paths can start at any node and end at any descendant, not just root-to-leaf. 2. Propose a brute-force solution first to establish a baseline, explaining its O(N^2) complexity, then pivot to the optimized approach. 3. Introduce the Prefix Sum technique with a HashMap to store cumulative sums encountered along the current recursion stack. 4. Detail the algorithm: calculate current prefix sum, check if (currentSum - targetSum) exists in the map, increment count if found, then recursively process children. 5. Emphasize the critical backtracking step: remove the current prefix sum from the map upon returning from recursion to ensure the map only contains valid ancestors for subsequent branches.

Key Points to Cover

  • Explicitly mention reducing time complexity from O(N^2) to O(N) using prefix sums
  • Demonstrate clear understanding of backtracking to maintain correct map state across different branches
  • Explain how the HashMap stores frequencies of prefix sums rather than just existence
  • Clarify that the path must be downward, connecting a node to one of its descendants
  • Show awareness of edge cases like empty trees or negative numbers affecting the sum logic

Sample Answer

To solve the Path Sum III problem efficiently, I would first acknowledge that a naive approach checking every node as a potential start point would result in O(N^2) time complexity. Since Google values scalable solutions…

Common Mistakes to Avoid

  • Failing to remove the current prefix sum from the HashMap after recursion, causing incorrect counts in sibling branches
  • Assuming paths must start at the root or end at a leaf, ignoring the specific problem constraints
  • Using a simple set instead of a HashMap, which fails when multiple paths share the same prefix sum value
  • Not handling the case where the current node's value itself equals the target sum without a preceding prefix

Sound confident on this question in 5 minutes

Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.

Try it free

Related Interview Questions

Convert Binary Tree to Doubly Linked List in Place

Hard
Microsoft

How do you implement a queue using two stacks?

Medium
Goldman Sachs

Design a Set with $O(1)$ `insert`, `remove`, and `check`

Easy
Cisco
Browse all 166 Data Structures questionsBrowse all 145 Google questions
Try this question free