Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonFacebookGoogle

Path Sum III (Any Path)

Choose your preparation mode4 modes available
🎯
Path Sum III (Any Path)
mediumTREEAmazonFacebookGoogle

Imagine tracking financial transactions in a tree-like ledger where you want to find all sequences of transactions summing to a target amount, regardless of where they start or end.

💡 This problem asks for counting all paths in a binary tree that sum to a target value, where paths can start and end anywhere but must go downwards. Beginners often struggle because paths are not restricted to root-to-leaf or root-to-node, making naive approaches inefficient and tricky to implement.
📋
Problem Statement

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The number of nodes in the tree is in the range [1, 10^5].-10^9 <= Node.val <= 10^9-10^9 <= targetSum <= 10^9
💡
Example
Input"root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8"
Output3

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

  • Single node tree where node.val == targetSum → output 1
  • Single node tree where node.val != targetSum → output 0
  • All nodes have zero value and targetSum is zero → output equals number of all possible downward paths
  • Tree with negative values and targetSum zero → paths can include negative values to sum zero
⚠️
Common Mistakes
Not resetting prefix sum counts after returning from recursion

Counts paths incorrectly across different branches, leading to wrong answer

✅ Decrement prefix sum count after recursive calls to backtrack

Assuming paths must start at root or leaf

Misses valid paths starting or ending in the middle of the tree

✅ Allow paths to start at any node by exploring all prefix sums

Using integer instead of long/long long for prefix sums

Integer overflow causes incorrect counts or runtime errors

✅ Use 64-bit integer types to store prefix sums

Not handling null nodes in recursion or iteration

Runtime errors or incorrect counts

✅ Check for null before processing nodes

Modifying global or class variables without resetting between test cases

Incorrect results on multiple test runs

✅ Initialize variables inside function or reset before each test

🧠
Brute Force (Check All Paths from Every Node)
💡 This approach exists to build intuition by exhaustively exploring every possible path starting from every node, helping beginners understand the problem's complexity before optimizing.

Intuition

For each node, explore all downward paths starting from it and count those that sum to targetSum. Repeat this for every node in the tree.

Algorithm

  1. Traverse each node in the tree.
  2. For each node, recursively explore all downward paths starting from it.
  3. Keep track of the running sum along the path.
  4. Increment count when running sum equals targetSum.
💡 The nested recursion can be confusing because it involves two levels: one to pick the start node, another to explore paths from that node.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root, targetSum):
        def dfs_from(node, current_sum):
            if not node:
                return 0
            current_sum += node.val
            count = 1 if current_sum == targetSum else 0
            count += dfs_from(node.left, current_sum)
            count += dfs_from(node.right, current_sum)
            return count

        if not root:
            return 0
        return dfs_from(root, 0) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

# Example usage:
# root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(2)), TreeNode(-3, None, TreeNode(11)))
# print(Solution().pathSum(root, 8))  # Output: 3
Line Notes
def dfs_from(node, current_sum):Defines helper to count paths starting at given node
if not node:Base case: no node means no path
current_sum += node.valAccumulate sum along current path
count = 1 if current_sum == targetSum else 0Increment count if path sum matches target
count += dfs_from(node.left, current_sum)Explore left subtree paths
count += dfs_from(node.right, current_sum)Explore right subtree paths
return dfs_from(root, 0) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)Sum counts from all nodes by recursive calls on root and subtrees
public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return dfsFrom(root, 0, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    private int dfsFrom(TreeNode node, int currentSum, int targetSum) {
        if (node == null) return 0;
        currentSum += node.val;
        int count = (currentSum == targetSum) ? 1 : 0;
        count += dfsFrom(node.left, currentSum, targetSum);
        count += dfsFrom(node.right, currentSum, targetSum);
        return count;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(10);
    //     root.left = new TreeNode(5);
    //     root.right = new TreeNode(-3);
    //     root.left.left = new TreeNode(3);
    //     root.left.right = new TreeNode(2);
    //     root.right.right = new TreeNode(11);
    //     Solution sol = new Solution();
    //     System.out.println(sol.pathSum(root, 8)); // Output: 3
    // }
}
Line Notes
if (root == null) return 0;Base case: empty tree has no paths
return dfsFrom(root, 0, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);Sum paths starting at root and recursively for left and right subtrees
private int dfsFrom(TreeNode node, int currentSum, int targetSum)Helper to count paths from a node
int count = (currentSum == targetSum) ? 1 : 0;Count path if sum matches target
count += dfsFrom(node.left, currentSum, targetSum);Explore left subtree
count += dfsFrom(node.right, currentSum, targetSum);Explore right subtree
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        return dfsFrom(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }

private:
    int dfsFrom(TreeNode* node, long long currentSum, int targetSum) {
        if (!node) return 0;
        currentSum += node->val;
        int count = (currentSum == targetSum) ? 1 : 0;
        count += dfsFrom(node->left, currentSum, targetSum);
        count += dfsFrom(node->right, currentSum, targetSum);
        return count;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(10);
//     root->left = new TreeNode(5);
//     root->right = new TreeNode(-3);
//     root->left->left = new TreeNode(3);
//     root->left->right = new TreeNode(2);
//     root->right->right = new TreeNode(11);
//     Solution sol;
//     cout << sol.pathSum(root, 8) << endl; // Output: 3
//     return 0;
// }
Line Notes
if (!root) return 0;Handle empty tree base case
return dfsFrom(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);Aggregate counts from root and subtrees
int dfsFrom(TreeNode* node, long long currentSum, int targetSum)Helper to count paths from node
int count = (currentSum == targetSum) ? 1 : 0;Count path if sum matches
count += dfsFrom(node->left, currentSum, targetSum);Explore left subtree
count += dfsFrom(node->right, currentSum, targetSum);Explore right subtree
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var pathSum = function(root, targetSum) {
    if (!root) return 0;
    function dfsFrom(node, currentSum) {
        if (!node) return 0;
        currentSum += node.val;
        let count = (currentSum === targetSum) ? 1 : 0;
        count += dfsFrom(node.left, currentSum);
        count += dfsFrom(node.right, currentSum);
        return count;
    }
    return dfsFrom(root, 0) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
};

// Example usage:
// let root = new TreeNode(10, new TreeNode(5, new TreeNode(3), new TreeNode(2)), new TreeNode(-3, null, new TreeNode(11)));
// console.log(pathSum(root, 8)); // Output: 3
Line Notes
if (!root) return 0;Base case for empty tree
function dfsFrom(node, currentSum)Helper to count paths from node
let count = (currentSum === targetSum) ? 1 : 0;Count path if sum matches target
count += dfsFrom(node.left, currentSum);Explore left subtree
count += dfsFrom(node.right, currentSum);Explore right subtree
return dfsFrom(root, 0) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);Sum counts from root and subtrees recursively
⏱
Complexity
TimeO(n^2) in worst case (skewed tree), O(n log n) average for balanced tree
SpaceO(h) recursion stack, where h is tree height

For each node, we explore all downward paths, leading to nested recursion. In skewed trees, this can be quadratic.

💡 For n=20 nodes, this could mean up to 400 path checks, which is inefficient but manageable for small inputs.
Interview Verdict: TLE on large inputs

This approach is too slow for large trees but is essential to understand the problem before optimizing.

🧠
Prefix Sum with DFS and Hash Map
💡 This approach uses prefix sums and a hash map to efficiently count paths, teaching beginners how to leverage extra data structures to optimize tree path problems.

Intuition

Track cumulative sums from root to current node and use a hash map to find how many prefix sums satisfy the condition that currentSum - prefixSum = targetSum, enabling O(n) counting.

Algorithm

  1. Initialize a hash map with {0:1} to count prefix sums.
  2. Traverse the tree with DFS, accumulating the current path sum.
  3. At each node, check if (currentSum - targetSum) exists in the map; add its count to result.
  4. Update the map with currentSum before exploring children and decrement after returning.
💡 The tricky part is updating the hash map correctly to avoid counting paths from different branches incorrectly.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root, targetSum):
        prefix_counts = {0: 1}
        self.result = 0

        def dfs(node, current_sum):
            if not node:
                return
            current_sum += node.val
            self.result += prefix_counts.get(current_sum - targetSum, 0)
            prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
            dfs(node.left, current_sum)
            dfs(node.right, current_sum)
            prefix_counts[current_sum] -= 1

        dfs(root, 0)
        return self.result

# Example usage:
# root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(2)), TreeNode(-3, None, TreeNode(11)))
# print(Solution().pathSum(root, 8))  # Output: 3
Line Notes
prefix_counts = {0: 1}Initialize map with sum 0 to count paths starting at root
self.result = 0Store total count of valid paths
self.result += prefix_counts.get(current_sum - targetSum, 0)Add count of prefix sums that form valid subpath
prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1Record current prefix sum before recursion
prefix_counts[current_sum] -= 1Remove current prefix sum after recursion to avoid affecting other branches
import java.util.HashMap;

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int result = 0;
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Long, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0L, 1);
        dfs(root, 0L, targetSum, prefixCounts);
        return result;
    }

    private void dfs(TreeNode node, long currentSum, int targetSum, HashMap<Long, Integer> prefixCounts) {
        if (node == null) return;
        currentSum += node.val;
        result += prefixCounts.getOrDefault(currentSum - targetSum, 0);
        prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);
        dfs(node.left, currentSum, targetSum, prefixCounts);
        dfs(node.right, currentSum, targetSum, prefixCounts);
        prefixCounts.put(currentSum, prefixCounts.get(currentSum) - 1);
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(10);
    //     root.left = new TreeNode(5);
    //     root.right = new TreeNode(-3);
    //     root.left.left = new TreeNode(3);
    //     root.left.right = new TreeNode(2);
    //     root.right.right = new TreeNode(11);
    //     Solution sol = new Solution();
    //     System.out.println(sol.pathSum(root, 8)); // Output: 3
    // }
}
Line Notes
HashMap<Long, Integer> prefixCounts = new HashMap<>();Map to store counts of prefix sums
prefixCounts.put(0L, 1);Initialize with sum 0 for paths starting at root
result += prefixCounts.getOrDefault(currentSum - targetSum, 0);Count valid subpaths ending at current node
prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);Add current prefix sum before recursion
prefixCounts.put(currentSum, prefixCounts.get(currentSum) - 1);Remove current prefix sum after recursion
#include <iostream>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int result = 0;
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> prefixCounts;
        prefixCounts[0] = 1;
        dfs(root, 0, targetSum, prefixCounts);
        return result;
    }

private:
    void dfs(TreeNode* node, long long currentSum, int targetSum, unordered_map<long long, int>& prefixCounts) {
        if (!node) return;
        currentSum += node->val;
        result += prefixCounts[currentSum - targetSum];
        prefixCounts[currentSum]++;
        dfs(node->left, currentSum, targetSum, prefixCounts);
        dfs(node->right, currentSum, targetSum, prefixCounts);
        prefixCounts[currentSum]--;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(10);
//     root->left = new TreeNode(5);
//     root->right = new TreeNode(-3);
//     root->left->left = new TreeNode(3);
//     root->left->right = new TreeNode(2);
//     root->right->right = new TreeNode(11);
//     Solution sol;
//     cout << sol.pathSum(root, 8) << endl; // Output: 3
//     return 0;
// }
Line Notes
unordered_map<long long, int> prefixCounts;Hash map to store prefix sums and counts
prefixCounts[0] = 1;Initialize with zero sum for root paths
result += prefixCounts[currentSum - targetSum];Add count of valid subpaths ending here
prefixCounts[currentSum]++;Add current prefix sum before recursion
prefixCounts[currentSum]--;Remove current prefix sum after recursion
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var pathSum = function(root, targetSum) {
    let prefixCounts = new Map();
    prefixCounts.set(0, 1);
    let result = 0;

    function dfs(node, currentSum) {
        if (!node) return;
        currentSum += node.val;
        result += prefixCounts.get(currentSum - targetSum) || 0;
        prefixCounts.set(currentSum, (prefixCounts.get(currentSum) || 0) + 1);
        dfs(node.left, currentSum);
        dfs(node.right, currentSum);
        prefixCounts.set(currentSum, prefixCounts.get(currentSum) - 1);
    }

    dfs(root, 0);
    return result;
};

// Example usage:
// let root = new TreeNode(10, new TreeNode(5, new TreeNode(3), new TreeNode(2)), new TreeNode(-3, null, new TreeNode(11)));
// console.log(pathSum(root, 8)); // Output: 3
Line Notes
let prefixCounts = new Map();Map to track prefix sums and their counts
prefixCounts.set(0, 1);Initialize with zero sum for root paths
result += prefixCounts.get(currentSum - targetSum) || 0;Add count of valid subpaths ending here
prefixCounts.set(currentSum, (prefixCounts.get(currentSum) || 0) + 1);Add current prefix sum before recursion
prefixCounts.set(currentSum, prefixCounts.get(currentSum) - 1);Remove current prefix sum after recursion
⏱
Complexity
TimeO(n)
SpaceO(n) for hash map and recursion stack

Each node is visited once, and prefix sums are updated in O(1) average time using a hash map.

💡 For n=20, this means roughly 20 operations plus map updates, which is efficient even for large trees.
Interview Verdict: Accepted

This is the optimal approach commonly expected in interviews for this problem.

🧠
Iterative DFS with Stack and Prefix Sum Map
💡 This approach shows how to implement the prefix sum method iteratively, useful for candidates who prefer iterative solutions or want to avoid recursion stack overflow.

Intuition

Use an explicit stack to simulate DFS traversal while maintaining prefix sums and a hash map to count valid paths, similar to the recursive approach.

Algorithm

  1. Use a stack to perform DFS traversal, storing nodes along with current prefix sum.
  2. Maintain a hash map of prefix sums and their counts.
  3. At each node, update the result by checking prefix sums that satisfy the target condition.
  4. After processing children, decrement prefix sum count to backtrack.
💡 Managing prefix sums and backtracking manually in iterative code is more complex but reinforces understanding of recursion.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                if node.right:
                    stack.append((node.right, current_sum, False))
                if node.left:
                    stack.append((node.left, current_sum, False))
            else:
                prefix_counts[current_sum] -= 1

        return result

# Example usage:
# root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(2)), TreeNode(-3, None, TreeNode(11)))
# print(Solution().pathSum(root, 8))  # Output: 3
Line Notes
stack = [(root, 0, False)]Initialize stack with root and sum 0, visited flag False
if not visited:Process node first time: update sums and push children
result += prefix_counts.get(current_sum - targetSum, 0)Count valid paths ending at current node
prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1Add current prefix sum count
prefix_counts[current_sum] -= 1Backtrack prefix sum count after children processed
import java.util.*;

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        Map<Long, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0L, 1);
        int result = 0;
        Deque<Object[]> stack = new ArrayDeque<>();
        stack.push(new Object[]{root, 0L, false});
        Deque<Long> pathStack = new ArrayDeque<>(); // Optional for clarity

        while (!stack.isEmpty()) {
            Object[] top = stack.pop();
            TreeNode node = (TreeNode) top[0];
            long currentSum = (Long) top[1];
            boolean visited = (Boolean) top[2];
            if (node == null) continue;
            if (!visited) {
                currentSum += node.val;
                result += prefixCounts.getOrDefault(currentSum - targetSum, 0);
                prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);
                stack.push(new Object[]{node, currentSum, true});
                if (node.right != null) stack.push(new Object[]{node.right, currentSum, false});
                if (node.left != null) stack.push(new Object[]{node.left, currentSum, false});
                pathStack.push(currentSum); // Track prefix sums for backtracking
            } else {
                prefixCounts.put(currentSum, prefixCounts.get(currentSum) - 1);
                pathStack.pop();
            }
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(10);
    //     root.left = new TreeNode(5);
    //     root.right = new TreeNode(-3);
    //     root.left.left = new TreeNode(3);
    //     root.left.right = new TreeNode(2);
    //     root.right.right = new TreeNode(11);
    //     Solution sol = new Solution();
    //     System.out.println(sol.pathSum(root, 8)); // Output: 3
    // }
}
Line Notes
Map<Long, Integer> prefixCounts = new HashMap<>();Map to track prefix sums and counts
stack.push(new Object[]{root, 0L, false});Initialize stack with root node and sum 0
if (!visited) {Process node first time: update sums and push children
result += prefixCounts.getOrDefault(currentSum - targetSum, 0);Count valid paths ending at current node
prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);Add current prefix sum count
prefixCounts.put(currentSum, prefixCounts.get(currentSum) - 1);Backtrack prefix sum count after children processed
pathStack.push(currentSum);Track prefix sums for backtracking (optional)
pathStack.pop();Remove prefix sum after backtracking (optional)
#include <iostream>
#include <unordered_map>
#include <stack>
#include <tuple>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        unordered_map<long long, int> prefixCounts;
        prefixCounts[0] = 1;
        int result = 0;
        stack<tuple<TreeNode*, long long, bool>> stk;
        stk.push({root, 0, false});

        while (!stk.empty()) {
            auto [node, currentSum, visited] = stk.top();
            stk.pop();
            if (!node) continue;
            if (!visited) {
                currentSum += node->val;
                result += prefixCounts[currentSum - targetSum];
                prefixCounts[currentSum]++;
                stk.push({node, currentSum, true});
                if (node->right) stk.push({node->right, currentSum, false});
                if (node->left) stk.push({node->left, currentSum, false});
            } else {
                prefixCounts[currentSum]--;
            }
        }
        return result;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(10);
//     root->left = new TreeNode(5);
//     root->right = new TreeNode(-3);
//     root->left->left = new TreeNode(3);
//     root->left->right = new TreeNode(2);
//     root->right->right = new TreeNode(11);
//     Solution sol;
//     cout << sol.pathSum(root, 8) << endl; // Output: 3
//     return 0;
// }
Line Notes
unordered_map<long long, int> prefixCounts;Map to store prefix sums and counts
stk.push({root, 0, false});Initialize stack with root and sum 0
if (!visited) {Process node first time: update sums and push children
result += prefixCounts[currentSum - targetSum];Count valid paths ending at current node
prefixCounts[currentSum]++;Add current prefix sum count
prefixCounts[currentSum]--;Backtrack prefix sum count after children processed
auto [node, currentSum, visited] = stk.top();Structured binding requires C++17 or later
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var pathSum = function(root, targetSum) {
    if (!root) return 0;
    let prefixCounts = new Map();
    prefixCounts.set(0, 1);
    let result = 0;
    let stack = [[root, 0, false]]; // node, currentSum, visited

    while (stack.length > 0) {
        let [node, currentSum, visited] = stack.pop();
        if (!node) continue;
        if (!visited) {
            currentSum += node.val;
            result += prefixCounts.get(currentSum - targetSum) || 0;
            prefixCounts.set(currentSum, (prefixCounts.get(currentSum) || 0) + 1);
            stack.push([node, currentSum, true]);
            if (node.right) stack.push([node.right, currentSum, false]);
            if (node.left) stack.push([node.left, currentSum, false]);
        } else {
            prefixCounts.set(currentSum, prefixCounts.get(currentSum) - 1);
        }
    }
    return result;
};

// Example usage:
// let root = new TreeNode(10, new TreeNode(5, new TreeNode(3), new TreeNode(2)), new TreeNode(-3, null, new TreeNode(11)));
// console.log(pathSum(root, 8)); // Output: 3
Line Notes
let prefixCounts = new Map();Map to track prefix sums and counts
stack = [[root, 0, false]];Initialize stack with root node and sum 0
if (!visited) {Process node first time: update sums and push children
result += prefixCounts.get(currentSum - targetSum) || 0;Count valid paths ending at current node
prefixCounts.set(currentSum, (prefixCounts.get(currentSum) || 0) + 1);Add current prefix sum count
prefixCounts.set(currentSum, prefixCounts.get(currentSum) - 1);Backtrack prefix sum count after children processed
⏱
Complexity
TimeO(n)
SpaceO(n) for stack and hash map

Each node is processed twice (enter and exit), and prefix sums updated in O(1) average time.

💡 This iterative method is as efficient as recursive but requires careful stack and map management.
Interview Verdict: Accepted

This approach is useful when recursion depth is a concern or interviewer requests iterative solution.

📊
All Approaches - One-Glance Tradeoffs
💡 The prefix sum with DFS and hash map approach is the best to implement in interviews due to its optimal time and space complexity.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2) worst caseO(h) recursion stackYes (deep recursion)NoMention only - never code
2. Prefix Sum with DFS and Hash MapO(n)O(n) for hash map and recursion stackYes (deep recursion)No (counts only)Code this approach
3. Iterative DFS with Stack and Prefix Sum MapO(n)O(n) for stack and hash mapNoNo (counts only)Optional - if asked for iterative
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and path definition (downward paths, any start/end).State brute force approach to show understanding of problem complexity.Explain inefficiency of brute force and motivate prefix sum optimization.Describe prefix sum with hash map approach and how it reduces complexity.If asked, discuss iterative implementation to avoid recursion.

Time Allocation

Clarify: 2min → Brute Force: 5min → Prefix Sum: 8min → Iterative: 5min → Testing & Discussion: 5min. Total ~25min

What the Interviewer Tests

Interviewer tests your understanding of tree traversal, prefix sums, hash map usage, and ability to optimize naive solutions.

Common Follow-ups

  • What if paths can go upwards or in any direction? → Use parent pointers or convert to graph.
  • How to output the actual paths, not just count? → Store path nodes during traversal.
  • Can this be done without extra space? → Not efficiently; prefix sums require extra storage.
  • What if targetSum is zero and nodes have negative values? → Prefix sum approach still works.
💡 These follow-ups test your ability to adapt the solution to variations and demonstrate deeper understanding.
🔍
Pattern Recognition

When to Use

1) Problem involves paths in a tree, 2) Paths can start/end anywhere but must go downwards, 3) Need to count or find sums equal to target, 4) Large input size requiring optimization.

Signature Phrases

path sum equals targetpaths can start or end anywheredownward paths onlycount number of paths

NOT This Pattern When

Problems requiring paths in graphs with cycles or paths that can go upwards and downwards are different and need graph algorithms.

Similar Problems

Path Sum I - simpler root-to-leaf path sumsPath Sum II - output all root-to-leaf paths with sumBinary Tree Maximum Path Sum - find max sum path anywhere

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.

Solution

  1. Step 1: Understand the problem constraints

    Reconstructing a binary tree from preorder and inorder requires knowing root positions quickly to split subtrees.
  2. Step 2: Identify the optimal approach

    Using a hash map for inorder indices allows O(1) root lookups, avoiding repeated O(n) searches in recursion.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Hash map lookup avoids repeated scanning [OK]
Hint: Hash map lookup avoids repeated inorder searches [OK]
Common Mistakes:
  • Assuming greedy or BFS can reconstruct tree correctly
  • Confusing DP with tree construction
  • Ignoring the need for quick root index lookup
2. Consider the following iterative postorder traversal code to compute the diameter of a binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final value of the variable diameter after the function completes?
easy
A. 2
B. 4
C. 1
D. 3

Solution

  1. Step 1: Trace heights and diameter updates for each node.

    Node 4: height=1, diameter=0; Node 2: left=1 (node4), right=0, diameter=max(0,1)=1; Node 3: height=1, diameter=1; Node 1: left=2 (node2), right=1 (node3), diameter=max(1,2+1=3)=3.
  2. Step 2: Verify final diameter value returned.

    The diameter is the maximum sum of left and right heights at any node, which is 3 edges, so the longest path length is 3 edges.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Longest path is from node 4 to node 3 with length 3 edges [OK]
Hint: Diameter counts edges, not nodes [OK]
Common Mistakes:
  • Confusing diameter as number of nodes
  • Off-by-one in height calculation
  • Missing right subtree height
3. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 5: rob_current calculation uses left[0] and right[0]
B. Line 7: Returning (rob_current, not_rob_current)
C. Line 6: not_rob_current uses max(left) + max(right)
D. Line 2: Base case returns (0, 0)

Solution

  1. Step 1: Understand rob_current calculation

    rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.
  2. Step 2: Identify the bug

    Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Using rob values of children overcounts and breaks correctness [OK]
Hint: Rob current node + not_rob children, not rob children [OK]
Common Mistakes:
  • Mixing rob and not_rob indices in tuple
  • Forgetting adjacency constraints
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. What is the space complexity of the Morris Preorder Traversal approach for summing root-to-leaf numbers in a binary tree with n nodes?
medium
A. O(1) because Morris traversal uses threaded binary tree links without extra stack
B. O(n) due to recursion stack in DFS
C. O(h) where h is tree height due to implicit stack usage
D. O(n) because all nodes are visited and stored temporarily

Solution

  1. Step 1: Identify space usage in Morris traversal

    Morris traversal modifies tree pointers temporarily to avoid recursion or explicit stack, so no extra stack space is used.
  2. Step 2: Confirm no auxiliary data structures

    Only constant extra variables (pointers and counters) are used, so space complexity is O(1).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Morris traversal is known for O(1) space by threading tree [OK]
Hint: Morris traversal avoids recursion and stack [OK]
Common Mistakes:
  • Confusing recursion stack with Morris traversal
  • Assuming O(h) due to tree height
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