Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonFacebookGoogle

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

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(N * L)O(L + K * L)Yes (deep recursion)YesMention and implement first
2. Backtracking with Early PruningO(N * L) but often betterO(L + K * L)YesYesMention as optimization if node values positive
3. Iterative DFS with StackO(N * L)O(L + K * L)NoYesUse 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/5)
1. Consider the following Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree: 1 / \ 2 3 What is the final value of the variable total returned by sumNumbers?
easy
A. 5
B. 15
C. 25
D. 26

Solution

  1. Step 1: Trace path 1->2

    current_number accumulates 1 then 12; leaf node 2 adds 12 to total.
  2. Step 2: Trace path 1->3

    current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.
  3. Step 3: Check for off-by-one or missed increments

    Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Sum of 12 and 13 is 25, matching code behavior [OK]
Hint: Trace current_number updates carefully at each node [OK]
Common Mistakes:
  • Off-by-one in current_number division
  • Adding non-leaf nodes to total
2. What is the time complexity of the optimal iterative postorder traversal algorithm for computing the maximum path sum in a binary tree with n nodes and height h?
medium
A. O(n) because each node is visited a constant number of times
B. O(n log n) due to repeated subtree computations
C. O(h * n) because the stack operations depend on tree height
D. O(n^2) in worst case due to nested traversal of subtrees

Solution

  1. Step 1: Identify node visits

    Each node is pushed and popped from the stack once, and gains are computed once per node.
  2. Step 2: Analyze stack operations and computations

    Stack size is at most h, but operations per node are constant, so total time is proportional to n.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Linear time traversal with constant work per node [OK]
Hint: Each node processed once, O(n) time [OK]
Common Mistakes:
  • Confusing stack height with repeated visits
  • Assuming nested loops cause O(n^2)
  • Thinking recursion stack adds multiplicative factor
3. What is the time complexity of the iterative postorder traversal using one stack and a pointer on a binary tree with n nodes?
medium
A. O(n log n) due to repeated stack operations
B. O(n) but with O(h) auxiliary space where h is tree height
C. O(n^2) because of nested while loops
D. O(n) because each node is visited and processed once

Solution

  1. Step 1: Analyze node visits

    Each node is pushed and popped exactly once, so operations proportional to n.
  2. Step 2: Confirm no nested repeated work

    Inner loops traverse down left children, but total iterations over all nodes sum to n.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Linear time complexity matches traversal of all nodes once [OK]
Hint: Each node processed once -> O(n) time [OK]
Common Mistakes:
  • Assuming nested loops multiply to n^2
  • Confusing auxiliary space with time
4. What is the time complexity of the BFS-based serialization and deserialization of a binary tree with n nodes, assuming the tree is balanced? Consider both serialization and deserialization separately.
medium
A. Serialization: O(n log n), Deserialization: O(n log n)
B. Serialization: O(n), Deserialization: O(n^2)
C. Serialization: O(n), Deserialization: O(n)
D. Serialization: O(n^2), Deserialization: O(n)

Solution

  1. Step 1: Analyze serialization time

    Each node is enqueued and dequeued exactly once, so serialization is O(n).
  2. Step 2: Analyze deserialization time

    Deserialization processes each node once, reconstructing the tree in O(n) time.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Both serialization and deserialization scale linearly with number of nodes [OK]
Hint: Each node is processed once in BFS serialization/deserialization [OK]
Common Mistakes:
  • Assuming deserialization is O(n^2) due to nested loops
  • Confusing tree height with number of nodes
  • Thinking serialization is O(n log n) due to queue operations
5. What is the space complexity of the optimized recursive DFS approach for checking if a binary tree is symmetric, assuming the tree has n nodes and height h?
medium
A. O(h) due to recursion stack depth proportional to tree height
B. O(1) since no extra space besides variables is used
C. O(n) because all nodes are stored in an auxiliary data structure
D. O(n) due to storing all nodes in a queue for BFS

Solution

  1. Step 1: Identify recursion stack usage

    The recursive calls go as deep as the height of the tree, so the recursion stack uses O(h) space.
  2. Step 2: Confirm no additional data structures store all nodes

    The algorithm does not use queues or arrays to store nodes; it only uses call stack and local variables.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Recursion stack space depends on tree height, not total nodes [OK]
Hint: Recursion stack space = tree height, not total nodes [OK]
Common Mistakes:
  • Confusing BFS queue space with DFS recursion stack
  • Assuming O(n) space due to node storage
  • Ignoring recursion stack space
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