Path Sum III (Any Path)

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2) worst case	O(h) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Prefix Sum with DFS and Hash Map	O(n)	O(n) for hash map and recursion stack	Yes (deep recursion)	No (counts only)	Code this approach
3. Iterative DFS with Stack and Prefix Sum Map	O(n)	O(n) for stack and hash map	No	No (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. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

    1
   / \
  2   3

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result

easy

A. [2, 1, 3]

B. [1, 2, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Trace first iteration with current=1

   Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.

2. Step 2: Trace second iteration with current=2

   Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).

3. Step 3: Detect thread at 2.right=1

   Since predecessor.right == current, reset 2.right=None, move current=1.right=3.

4. Step 4: Trace current=3

   Node 3 has no left child, append 3, move current=3.right=None, loop ends.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Output matches preorder traversal [1,2,3] [OK]

Hint: Morris preorder appends root before left subtree [OK]

Common Mistakes:

• Appending nodes in wrong order
• Not resetting threaded links
• Confusing left and right child traversal

2. You need to convert a binary tree into a string and then reconstruct the exact same tree from that string. Which approach guarantees that the tree structure, including null children, is preserved and can be reconstructed efficiently?

easy

A. Use level order traversal (BFS) including null markers for missing children, then deserialize by reading nodes level by level.

B. Use a greedy traversal that records only node values without null markers, then reconstruct by inserting nodes in order.

C. Use dynamic programming to store subtree encodings and reconstruct from stored subtrees.

D. Use inorder traversal without null markers and reconstruct by assuming a balanced tree.

Solution

1. Step 1: Understand the need for null markers

   Without null markers, the tree structure cannot be uniquely reconstructed because missing children are ambiguous.

2. Step 2: Recognize BFS with null markers preserves structure

   Level order traversal with null markers records nodes level by level, capturing the exact shape of the tree, enabling correct deserialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Level order with null markers uniquely encodes tree structure [OK]

Hint: Null markers are essential to preserve tree shape [OK]

Common Mistakes:

• Ignoring null markers leads to ambiguous deserialization
• Assuming inorder traversal alone can reconstruct arbitrary trees
• Using greedy or DP approaches that don't preserve structure

3. Consider the following buggy code for inverting a binary tree. Which line contains the subtle bug that causes incorrect inversion?

medium

A. Line 3: Swapping children before recursive calls

B. Line 5: Recursive call on right child

C. Line 4: Recursive call on left child

D. Line 2: Missing check for empty tree

Solution

1. Step 1: Analyze order of operations

   The code swaps children before recursively inverting subtrees, which means subtrees are swapped but not inverted themselves.

2. Step 2: Identify why swapping before recursion is incorrect

   Swapping first causes recursion to invert the wrong subtrees, leading to partial or incorrect inversion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping must happen after recursive calls to invert subtrees correctly [OK]

Hint: Swap after recursion, not before, to invert subtrees properly [OK]

Common Mistakes:

• Swapping children before recursion
• Ignoring null root checks
• Confusing left and right subtree recursion order

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}

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

5. Suppose the binary tree nodes can have an arbitrary number of children (not just two). Which modification to the BFS-based maximum depth algorithm correctly computes the maximum depth in this scenario?

hard

A. Replace 'if node.left' and 'if node.right' checks with iterating over 'node.children' list and enqueue each child.

B. Keep the same code but only enqueue 'node.left' and 'node.right' if they exist, ignoring other children.

C. Use DFS recursion only, as BFS cannot handle nodes with more than two children.

D. Modify the code to sum depths of all children instead of taking the maximum.

Solution

1. Step 1: Understand the problem extension

   Nodes now have arbitrary children, so left/right pointers are insufficient.

2. Step 2: Modify BFS to handle multiple children

   Iterate over 'node.children' list and enqueue each child to explore all branches correctly.

3. Step 3: Evaluate other options

   Ignoring children misses nodes; DFS can work but BFS is still valid; summing depths is incorrect for max depth.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Enqueue all children ensures full traversal for max depth [OK]

Hint: Enqueue all children nodes to handle arbitrary branching [OK]

Common Mistakes:

• Ignoring extra children
• Assuming binary tree structure
• Summing depths instead of max