Path Sum II (All Root-to-Leaf Paths)

🎯

Path Sum II (All Root-to-Leaf Paths)

mediumTREEAmazonFacebookGoogle

Imagine navigating a maze where you want to find all routes from the entrance to the exit that add up to a certain score. This problem is about finding all root-to-leaf paths in a binary tree whose node values sum to a target.

💡 This problem is a classic example of using depth-first search (DFS) with backtracking to explore all possible paths in a tree. Beginners often struggle because they confuse path existence with path collection and may not know how to efficiently track and backtrack paths during recursion.

📋

Problem Statement

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. A leaf is a node with no children. Each path should be returned as a list of the node values, and the collection of paths should be returned as a list of lists.

The number of nodes in the tree is in the range [1, 5000]-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000000

💡

Example

Input"root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22"

Output[[5,4,11,2],[5,8,4,5]]

There are two root-to-leaf paths where the sum is 22: 5->4->11->2 and 5->8->4->5.

• Single node tree where node value equals targetSum → output is [[node.val]]
• Single node tree where node value does not equal targetSum → output is []
• Tree with negative values and targetSum that requires including negative nodes → output includes paths with negative values
• Tree where no root-to-leaf path sums to targetSum → output is []

⚠️

Common Mistakes

Adding path to results before confirming leaf node

Includes incomplete paths that do not end at leaves

✅ Check if node is leaf before adding path to results

Not backtracking (not removing last node from path after recursion)

Paths get mixed up, resulting in incorrect or duplicated paths

✅ Always remove last node from path after recursive calls

Pruning when node values can be negative

Misses valid paths that include negative values, causing incorrect results

✅ Only prune if all node values are guaranteed positive

Modifying path list in place without copying when adding to results

All results point to the same path object, leading to incorrect final output

✅ Add a copy of the current path (e.g., path[:], new ArrayList<>(path)) to results

Not handling empty tree input

Code may throw null pointer exceptions or return wrong output

✅ Check if root is null and return empty list immediately

🧠

Brute Force (Pure Recursion with Path Tracking)

💡 Starting with brute force helps understand the problem deeply by exploring all root-to-leaf paths without optimization. It builds intuition about recursion and backtracking, which is essential before optimizing.

Intuition

Traverse the tree from root to leaf, keep track of the current path and sum, and whenever a leaf is reached, check if the sum matches targetSum. If yes, record the path.

Algorithm

1. Start DFS from the root with an empty path and initial sum 0.
2. At each node, add its value to the current path and sum.
3. If the node is a leaf, check if the sum equals targetSum; if yes, add the path to results.
4. Recursively explore left and right children, then backtrack by removing the current node from the path.

💡 The challenge is to correctly add and remove nodes from the path during recursion to avoid mixing paths and to only add valid paths at leaves.

</>

Code

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    res = []
    def dfs(node, current_path, current_sum):
        if not node:
            return
        current_path.append(node.val)
        current_sum += node.val
        if not node.left and not node.right:
            if current_sum == targetSum:
                res.append(current_path[:])
        else:
            dfs(node.left, current_path, current_sum)
            dfs(node.right, current_path, current_sum)
        current_path.pop()

    dfs(root, [], 0)
    return res

# Example usage:
# Construct the tree from example
# root = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))), TreeNode(8, TreeNode(13), TreeNode(4, TreeNode(5), TreeNode(1))))
# print(pathSum(root, 22))

Line Notes

def dfs(node, current_path, current_sum):Defines the recursive DFS helper function with current node, path, and sum to explore all paths

if not node:Base case: if node is None, stop recursion to avoid errors

current_path.append(node.val)Add current node's value to path to track the current traversal

if not node.left and not node.right:Check if current node is a leaf to decide if path can be considered

if current_sum == targetSum:If leaf and sum matches target, record a copy of the current path

current_path.pop()Backtrack by removing the current node before returning to explore other paths

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), 0, res);
        return res;
    }
    private void dfs(TreeNode node, int targetSum, List<Integer> path, int currentSum, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        currentSum += node.val;
        if (node.left == null && node.right == null) {
            if (currentSum == targetSum) {
                res.add(new ArrayList<>(path));
            }
        } else {
            dfs(node.left, targetSum, path, currentSum, res);
            dfs(node.right, targetSum, path, currentSum, res);
        }
        path.remove(path.size() - 1);
    }

    // Example main to test
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);

        Solution sol = new Solution();
        System.out.println(sol.pathSum(root, 22));
    }
}

Line Notes

public List<List<Integer>> pathSum(TreeNode root, int targetSum)Entry point to start DFS and collect all valid paths

if (node == null) return;Base case to stop recursion on null nodes to prevent errors

path.add(node.val);Add current node to path to track traversal

if (node.left == null && node.right == null)Check if current node is a leaf to consider path validity

res.add(new ArrayList<>(path));Add a copy of current path to results to avoid mutation issues

path.remove(path.size() - 1);Backtrack by removing last node before returning to explore other paths

#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(root, targetSum, 0, path, res);
        return res;
    }
private:
    void dfs(TreeNode* node, int targetSum, int currentSum, vector<int>& path, vector<vector<int>>& res) {
        if (!node) return;
        path.push_back(node->val);
        currentSum += node->val;
        if (!node->left && !node->right) {
            if (currentSum == targetSum) {
                res.push_back(path);
            }
        } else {
            dfs(node->left, targetSum, currentSum, path, res);
            dfs(node->right, targetSum, currentSum, path, res);
        }
        path.pop_back();
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(5);
//     root->left = new TreeNode(4);
//     root->right = new TreeNode(8);
//     root->left->left = new TreeNode(11);
//     root->left->left->left = new TreeNode(7);
//     root->left->left->right = new TreeNode(2);
//     root->right->left = new TreeNode(13);
//     root->right->right = new TreeNode(4);
//     root->right->right->left = new TreeNode(5);
//     root->right->right->right = new TreeNode(1);
//     Solution sol;
//     vector<vector<int>> result = sol.pathSum(root, 22);
//     for (auto &path : result) {
//         for (int v : path) cout << v << " ";
//         cout << endl;
//     }
//     return 0;
// }

Line Notes

void dfs(TreeNode* node, int targetSum, int currentSum, vector<int>& path, vector<vector<int>>& res)Recursive DFS helper with current node, sum, path, and results to explore all paths

if (!node) return;Stop recursion on null nodes to avoid errors

path.push_back(node->val);Add current node to path to track traversal

if (!node->left && !node->right)Check if node is leaf to consider path validity

res.push_back(path);Add current path to results if sum matches target

path.pop_back();Backtrack by removing last node before returning to explore other paths

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var pathSum = function(root, targetSum) {
    const res = [];
    function dfs(node, currentPath, currentSum) {
        if (!node) return;
        currentPath.push(node.val);
        currentSum += node.val;
        if (!node.left && !node.right) {
            if (currentSum === targetSum) {
                res.push([...currentPath]);
            }
        } else {
            dfs(node.left, currentPath, currentSum);
            dfs(node.right, currentPath, currentSum);
        }
        currentPath.pop();
    }
    dfs(root, [], 0);
    return res;
};

// Example usage:
// const root = new TreeNode(5,
//     new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
//     new TreeNode(8, new TreeNode(13), new TreeNode(4, new TreeNode(5), new TreeNode(1)))
// );
// console.log(pathSum(root, 22));

Line Notes

function dfs(node, currentPath, currentSum)Recursive DFS helper to explore all root-to-leaf paths with current node, path, and sum

if (!node) return;Stop recursion on null nodes to avoid errors

currentPath.push(node.val);Add current node to path to track traversal

if (!node.left && !node.right)Check if node is leaf to consider path validity

res.push([...currentPath]);Add a copy of current path to results if sum matches target

currentPath.pop();Backtrack by removing last node before returning to explore other paths

⏱

Complexity

TimeO(N * L) where N is number of nodes and L is average path length

SpaceO(L) recursion stack + O(K * L) for storing paths, K is number of valid paths

We visit each node once, but copying paths to results takes extra time proportional to path length. The recursion stack and path list use space proportional to tree height.

💡 For a tree with 20 nodes and height 5, this means roughly 20 visits and storing paths of length up to 5, which is manageable but can grow large for bigger trees.

Interview Verdict: Accepted

This approach is straightforward and accepted for the problem constraints, but may be inefficient for very large trees with many paths.

🧠

Backtracking with Early Pruning

💡 This approach improves on brute force by stopping exploration early when the current sum exceeds targetSum, reducing unnecessary recursion especially when node values are positive.

Intuition

While traversing, if the current sum exceeds targetSum, no need to continue down that path because adding more positive values will only increase the sum.

Algorithm

1. Start DFS from root with empty path and sum 0.
2. Add current node value to path and sum.
3. If sum exceeds targetSum and all node values are positive, backtrack immediately.
4. If leaf and sum equals targetSum, add path to results.
5. Recursively explore children with pruning.
6. Backtrack by removing current node from path.

💡 The key is to recognize when continuing recursion is futile and stop early, which requires understanding node value constraints.

</>

Code

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    res = []
    def dfs(node, current_path, current_sum):
        if not node:
            return
        current_path.append(node.val)
        current_sum += node.val
        # Early pruning if current_sum > targetSum and all values positive
        if current_sum > targetSum and node.val > 0:
            current_path.pop()
            return
        if not node.left and not node.right:
            if current_sum == targetSum:
                res.append(current_path[:])
        else:
            dfs(node.left, current_path, current_sum)
            dfs(node.right, current_path, current_sum)
        current_path.pop()

    dfs(root, [], 0)
    return res

# Example usage as before

Line Notes

if current_sum > targetSum and node.val > 0:Prune paths early when sum exceeds target and node values are positive to reduce unnecessary recursion

current_path.pop()Backtrack immediately after pruning to maintain correct path state

if not node.left and not node.right:Check leaf node to add valid path if sum matches

res.append(current_path[:])Add a copy of current path to results to avoid mutation issues

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), 0, res);
        return res;
    }
    private void dfs(TreeNode node, int targetSum, List<Integer> path, int currentSum, List<List<Integer>> res) {
        if (node == null) return;
        path.add(node.val);
        currentSum += node.val;
        if (currentSum > targetSum && node.val > 0) {
            path.remove(path.size() - 1);
            return;
        }
        if (node.left == null && node.right == null) {
            if (currentSum == targetSum) {
                res.add(new ArrayList<>(path));
            }
        } else {
            dfs(node.left, targetSum, path, currentSum, res);
            dfs(node.right, targetSum, path, currentSum, res);
        }
        path.remove(path.size() - 1);
    }

    // main() same as before
}

Line Notes

if (currentSum > targetSum && node.val > 0)Prune recursion early when sum exceeds target and node values positive to optimize search

path.remove(path.size() - 1);Backtrack after pruning or after recursion to maintain correct path

if (node.left == null && node.right == null)Check leaf node for valid path

res.add(new ArrayList<>(path));Add copy of path to results to avoid mutation issues

#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(root, targetSum, 0, path, res);
        return res;
    }
private:
    void dfs(TreeNode* node, int targetSum, int currentSum, vector<int>& path, vector<vector<int>>& res) {
        if (!node) return;
        path.push_back(node->val);
        currentSum += node->val;
        if (currentSum > targetSum && node->val > 0) {
            path.pop_back();
            return;
        }
        if (!node->left && !node->right) {
            if (currentSum == targetSum) {
                res.push_back(path);
            }
        } else {
            dfs(node->left, targetSum, currentSum, path, res);
            dfs(node->right, targetSum, currentSum, path, res);
        }
        path.pop_back();
    }
};

// main() same as before

Line Notes

if (currentSum > targetSum && node->val > 0)Prune recursion early when sum exceeds target and node values positive to reduce unnecessary calls

path.pop_back();Backtrack after pruning or recursion to maintain correct path state

if (!node->left && !node->right)Check leaf node for valid path

res.push_back(path);Add current path to results if sum matches target

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var pathSum = function(root, targetSum) {
    const res = [];
    function dfs(node, currentPath, currentSum) {
        if (!node) return;
        currentPath.push(node.val);
        currentSum += node.val;
        if (currentSum > targetSum && node.val > 0) {
            currentPath.pop();
            return;
        }
        if (!node.left && !node.right) {
            if (currentSum === targetSum) {
                res.push([...currentPath]);
            }
        } else {
            dfs(node.left, currentPath, currentSum);
            dfs(node.right, currentPath, currentSum);
        }
        currentPath.pop();
    }
    dfs(root, [], 0);
    return res;
};

// Example usage same as before

Line Notes

if (currentSum > targetSum && node.val > 0)Prune recursion early when sum exceeds target and node values positive to optimize search

currentPath.pop();Backtrack after pruning or recursion to maintain correct path

if (!node.left && !node.right)Check leaf node for valid path

res.push([...currentPath]);Add copy of current path to results to avoid mutation issues

⏱

Complexity

TimeO(N * L) in worst case, but often better due to pruning

SpaceO(L) recursion stack + O(K * L) for storing paths

Pruning reduces the number of recursive calls when sums exceed targetSum, especially effective if node values are positive.

💡 For trees with positive values, pruning can significantly reduce work, but if negative values exist, pruning is less effective.

Interview Verdict: Accepted with optimization

This approach is better than brute force in many cases but depends on node values; still accepted and recommended when values are positive.

🧠

Iterative DFS with Stack and Path Tracking

💡 This approach uses an explicit stack to simulate recursion, which is useful in languages or environments where recursion depth is limited or to demonstrate iterative problem solving.

Intuition

Use a stack to store nodes along with the current path and sum. Pop nodes, check if leaf and sum matches, else push children with updated path and sum.

Algorithm

1. Initialize a stack with the root node, path containing root value, and current sum as root value.
2. While stack not empty, pop top element.
3. If node is leaf and sum equals targetSum, add path to results.
4. Else push children with updated path and sum onto stack.
5. Continue until stack is empty.

💡 Managing the path explicitly in the stack is tricky but helps avoid recursion and stack overflow.

</>

Code

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    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

# Example usage same as before

Line Notes

stack = [(root, [root.val], root.val)]Initialize stack with root node, path, and sum to start iterative DFS

while stack:Process nodes until stack is empty to explore all paths

node, path, current_sum = stack.pop()Pop current node and its path and sum information

if not node.left and not node.right:Check if current node is a leaf to consider path validity

res.append(path)Add valid path to results if sum matches target

stack.append((node.right, path + [node.right.val], current_sum + node.right.val))Push right child with updated path and sum onto stack

stack.append((node.left, path + [node.left.val], current_sum + node.left.val))Push left child similarly to continue DFS

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<NodeState> stack = new ArrayDeque<>();
        stack.push(new NodeState(root, new ArrayList<>(Arrays.asList(root.val)), root.val));
        while (!stack.isEmpty()) {
            NodeState curr = stack.pop();
            TreeNode node = curr.node;
            List<Integer> path = curr.path;
            int sum = curr.sum;
            if (node.left == null && node.right == null) {
                if (sum == targetSum) {
                    res.add(path);
                }
            }
            if (node.right != null) {
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(node.right.val);
                stack.push(new NodeState(node.right, newPath, sum + node.right.val));
            }
            if (node.left != null) {
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(node.left.val);
                stack.push(new NodeState(node.left, newPath, sum + node.left.val));
            }
        }
        return res;
    }

    private static class NodeState {
        TreeNode node;
        List<Integer> path;
        int sum;
        NodeState(TreeNode node, List<Integer> path, int sum) {
            this.node = node;
            this.path = path;
            this.sum = sum;
        }
    }

    // main() same as before
}

Line Notes

Deque<NodeState> stack = new ArrayDeque<>();Use stack to hold nodes with path and sum info for iterative DFS

stack.push(new NodeState(root, new ArrayList<>(Arrays.asList(root.val)), root.val));Initialize stack with root node and its path and sum

NodeState curr = stack.pop();Pop current node state to process

if (node.left == null && node.right == null)Check if current node is leaf to consider path validity

res.add(path);Add valid path to results if sum matches target

stack.push(new NodeState(node.right, newPath, sum + node.right.val));Push right child with updated path and sum onto stack

stack.push(new NodeState(node.left, newPath, sum + node.left.val));Push left child similarly to continue DFS

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

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

struct NodeState {
    TreeNode* node;
    vector<int> path;
    int sum;
    NodeState(TreeNode* n, vector<int> p, int s) : node(n), path(move(p)), sum(s) {}
};

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        if (!root) return res;
        stack<NodeState> stk;
        stk.push(NodeState(root, {root->val}, root->val));
        while (!stk.empty()) {
            NodeState curr = stk.top(); stk.pop();
            TreeNode* node = curr.node;
            vector<int> path = curr.path;
            int sum = curr.sum;
            if (!node->left && !node->right) {
                if (sum == targetSum) {
                    res.push_back(path);
                }
            }
            if (node->right) {
                vector<int> newPath = path;
                newPath.push_back(node->right->val);
                stk.push(NodeState(node->right, newPath, sum + node->right->val));
            }
            if (node->left) {
                vector<int> newPath = path;
                newPath.push_back(node->left->val);
                stk.push(NodeState(node->left, newPath, sum + node->left->val));
            }
        }
        return res;
    }
};

// main() same as before

Line Notes

stack<NodeState> stk;Stack to hold nodes with path and sum info for iterative DFS

stk.push(NodeState(root, {root->val}, root->val));Initialize stack with root node and its path and sum

NodeState curr = stk.top(); stk.pop();Pop current node state to process

if (!node->left && !node->right)Check if current node is leaf to consider path validity

res.push_back(path);Add valid path to results if sum matches target

stk.push(NodeState(node->right, newPath, sum + node->right->val));Push right child with updated path and sum onto stack

stk.push(NodeState(node->left, newPath, sum + node->left->val));Push left child similarly to continue DFS

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var pathSum = function(root, targetSum) {
    if (!root) return [];
    const res = [];
    const stack = [{node: root, path: [root.val], sum: root.val}];
    while (stack.length > 0) {
        const {node, path, sum} = stack.pop();
        if (!node.left && !node.right) {
            if (sum === targetSum) {
                res.push(path);
            }
        }
        if (node.right) {
            stack.push({node: node.right, path: [...path, node.right.val], sum: sum + node.right.val});
        }
        if (node.left) {
            stack.push({node: node.left, path: [...path, node.left.val], sum: sum + node.left.val});
        }
    }
    return res;
};

// Example usage same as before

Line Notes

const stack = [{node: root, path: [root.val], sum: root.val}];Initialize stack with root node and its path and sum for iterative DFS

while (stack.length > 0)Process nodes until stack is empty to explore all paths

const {node, path, sum} = stack.pop();Pop current node state to process

if (!node.left && !node.right)Check if current node is leaf to consider path validity

res.push(path);Add valid path to results if sum matches target

stack.push({node: node.right, path: [...path, node.right.val], sum: sum + node.right.val});Push right child with updated path and sum onto stack

stack.push({node: node.left, path: [...path, node.left.val], sum: sum + node.left.val});Push left child similarly to continue DFS

⏱

Complexity

TimeO(N * L) where N is nodes and L is path length

SpaceO(L) stack + O(K * L) for storing paths

Iterative DFS visits each node once and stores paths explicitly, which can be costly but avoids recursion stack overflow.

💡 For large trees, iterative approach prevents stack overflow errors common in recursion.

Interview Verdict: Accepted

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

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the recursive brute force with backtracking is sufficient and fastest to implement. Pruning is a nice optimization if node values are positive. Iterative DFS is useful if recursion depth is a concern.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(N * L)	O(L + K * L)	Yes (deep recursion)	Yes	Mention and implement first
2. Backtracking with Early Pruning	O(N * L) but often better	O(L + K * L)	Yes	Yes	Mention as optimization if node values positive
3. Iterative DFS with Stack	O(N * L)	O(L + K * L)	No	Yes	Use if recursion depth is a concern or asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize if possible, and test thoroughly.

How to Present

Clarify the problem and confirm input/output format.Describe brute force DFS approach to find all root-to-leaf paths and check sums.Mention possible pruning optimization if node values are positive.If asked, provide iterative DFS solution to avoid recursion.Write clean code and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of DFS, backtracking, path tracking, and ability to handle edge cases and optimize recursion.

Common Follow-ups

• What if node values can be negative? → pruning may not work, must explore all paths.
• Can you do this iteratively? → yes, use stack to simulate recursion.

💡 These follow-ups test your grasp of pruning limitations and iterative DFS implementation.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree traversal; 2) Need to find all root-to-leaf paths; 3) Condition depends on sum of node values; 4) Output requires collecting all valid paths.

Signature Phrases

all root-to-leaf pathssum equals targetreturn all paths

NOT This Pattern When

Problems that only ask for existence of a path or maximum/minimum path sums without collecting all paths.

Similar Problems

Path Sum I - only check if any path exists with sumBinary Tree Paths - collect all root-to-leaf paths regardless of sumSum Root to Leaf Numbers - sum numeric values formed by root-to-leaf paths

Practice

1. Consider the following iterative postorder traversal code to compute the maximum path sum in a binary tree. Given the tree below, what is the final value of max_sum after the function completes? Tree structure: ``` 1 / 2 3 ```

class TreeNode:
    def __init__(self, val=0, left=null, right=null):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    stack = []
    node = root
    last_visited = null
    gain_map = {}

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_gain = max(gain_map.get(peek.left, 0), 0)
                right_gain = max(gain_map.get(peek.right, 0), 0)
                current_path_sum = peek.val + left_gain + right_gain
                max_sum = max(max_sum, current_path_sum)
                gain_map[peek] = peek.val + max(left_gain, right_gain)
                last_visited = stack.pop()
    return max_sum

easy

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Trace left subtree gain

   Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.

2. Step 2: Trace root and right subtree

   Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of path 2 -> 1 -> 3 is 6 [OK]

Hint: Sum path 2->1->3 yields max sum 6 [OK]

Common Mistakes:

• Ignoring one child's gain leads to 5 or 4
• Off-by-one in gain_map updates
• Returning partial sums instead of max path sum

2. You are given a binary tree and asked to transform it into a singly linked list in-place such that the linked list follows the preorder traversal of the tree. Which approach guarantees an optimal solution with O(n) time and O(h) space complexity, where h is the tree height?

easy

A. Use a reverse preorder traversal (right subtree first, then left) with a global pointer to rewire nodes in-place.

B. Perform a preorder traversal, store nodes in a list, then rebuild the linked list from the list.

C. Use a bottom-up postorder traversal to reconstruct the linked list from leaves to root.

D. Apply a greedy approach that always attaches the left subtree to the rightmost node of the right subtree.

Solution

1. Step 1: Understand traversal order needed

   The linked list must follow preorder traversal (root, left, right).

2. Step 2: Identify approach that rewires in-place efficiently

   Reverse preorder traversal (right, left) with a global pointer allows rewiring nodes in-place without extra storage, achieving O(n) time and O(h) space due to recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reverse preorder traversal with global pointer rewires nodes in correct order [OK]

Hint: Reverse preorder traversal with global pointer is optimal [OK]

Common Mistakes:

• Using extra space to store nodes before rebuilding
• Confusing traversal order causing incorrect linked list
• Trying greedy rewiring without correct traversal order

3. You are given a binary tree and need to find the longest path from the root node down to the farthest leaf node. Which algorithmic approach guarantees an optimal solution to determine this maximum depth?

easy

A. Dynamic Programming with memoization on node values

B. Greedy traversal picking the first child node at each step

C. Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all nodes

D. Sorting nodes by value and selecting the deepest node

Solution

1. Step 1: Understand the problem requires exploring all paths from root to leaves

   Finding maximum depth means checking every path from root to leaves, so partial or greedy approaches won't guarantee correctness.

2. Step 2: Identify algorithms that explore all nodes

   DFS or BFS traverse all nodes systematically, ensuring the maximum depth is found. Greedy or sorting approaches do not consider all paths.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DFS and BFS both visit all nodes to find max depth [OK]

Hint: Max depth requires full traversal, not greedy or sorting [OK]

Common Mistakes:

• Assuming greedy traversal finds max depth
• Confusing max depth with max node value
• Thinking sorting nodes helps depth calculation

4. Given a binary tree where each root-to-leaf path represents a number formed by concatenating node values, which algorithmic approach guarantees computing the sum of all such numbers efficiently without missing any path or double counting partial paths?

easy

A. Depth-first search (DFS) that accumulates the current number along the path and adds it only at leaf nodes

B. Dynamic programming that stores sums for subtrees and combines them at the root

C. Greedy traversal that sums node values at each level independently

D. Breadth-first search (BFS) that sums values of nodes at each depth and multiplies by depth

Solution

1. Step 1: Understand problem requirements

   The problem requires summing numbers formed by concatenating node values from root to leaf, so partial paths must not be summed prematurely.

2. Step 2: Identify correct traversal pattern

   DFS naturally explores root-to-leaf paths, allowing accumulation of the current number and summing only at leaf nodes, ensuring correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS accumulates path values correctly and sums only at leaves [OK]

Hint: Sum only at leaves during DFS traversal [OK]

Common Mistakes:

• Summing at non-leaf nodes
• Using BFS without path tracking

5. 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