Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonGoogleFacebook

Sum Root to Leaf Numbers

Choose your preparation mode4 modes available
🎯
Sum Root to Leaf Numbers
mediumTREEAmazonGoogleFacebook

Imagine you have a tree where each node holds a digit, and you want to find the sum of all numbers formed by root-to-leaf paths - like reading numbers off branches in a magical forest.

💡 This problem is about traversing a tree and accumulating values along paths. Beginners often struggle because they must carry partial results down the recursion and only add to the total at leaves, which requires understanding both DFS and how to pass state.
📋
Problem Statement

Given a binary tree where each node contains a single digit (0-9), each root-to-leaf path represents a number formed by concatenating the digits along the path. Return the total sum of all these numbers. A leaf is a node with no children.

The number of nodes in the tree is in the range [1, 10^5].Node values are digits from 0 to 9.
💡
Example
Input"root = [1,2,3]"
Output25

There are two root-to-leaf paths: 1->2 represents 12, 1->3 represents 13. Sum is 12 + 13 = 25.

Input"root = [4,9,0,5,1]"
Output1026

Paths: 4->9->5 = 495, 4->9->1 = 491, 4->0 = 40. Sum = 495 + 491 + 40 = 1026.

  • Single node tree → output is the node's value
  • Tree with all nodes having value 0 → sum is 0
  • Tree with only left children → sum is the single number formed by concatenation
  • Tree with only right children → sum is the single number formed by concatenation
⚠️
Common Mistakes
Adding current number to total at non-leaf nodes

Sum includes incomplete numbers, resulting in incorrect total

✅ Only add to total when node is a leaf (no children)

Not carrying the current number correctly during recursion

Numbers formed are incorrect, leading to wrong sums

✅ Update current number as current_number * 10 + node.val at each step

Forgetting to handle empty tree (null root)

Code may crash or return wrong result

✅ Check if root is null and return 0 immediately

Using global or class variable without resetting between calls

Multiple calls to function produce wrong results due to leftover state

✅ Initialize or reset accumulator variables inside the function

Integer overflow when forming numbers in languages with fixed int size

Incorrect sums or runtime errors on large trees

✅ Use long/int64 types or handle large numbers carefully

🧠
Brute Force (Pure Recursion)
💡 Starting with pure recursion helps understand how to traverse all root-to-leaf paths and accumulate numbers without any optimization. It builds the foundation for carrying state in DFS.

Intuition

Traverse the tree from root to leaf, at each node append the digit to a running number, and when a leaf is reached, add the number to a global sum.

Algorithm

  1. Start DFS from the root with initial current number 0.
  2. At each node, update current number by current_number * 10 + node's digit.
  3. If the node is a leaf, add current number to total sum.
  4. Recursively call DFS on left and right children if they exist.
💡 The challenge is to carry the partial number correctly and only add to sum at leaves, which is easy to miss at first.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            if not node.left and not node.right:
                self.total += current_number
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total

# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(3))
# print(Solution().sumNumbers(root))  # Output: 25
Line Notes
self.total = 0Initialize total sum to accumulate all root-to-leaf numbers
def dfs(node, current_number):Define recursive DFS helper carrying current number formed so far
if not node:Base case: if node is None, stop recursion
current_number = current_number * 10 + node.valAppend current node's digit to the number formed so far
if not node.left and not node.right:Check if current node is a leaf to add current number to total
self.total += current_numberAdd the complete number formed from root to this leaf
dfs(node.left, current_number)Recurse left subtree with updated number
dfs(node.right, current_number)Recurse right subtree with updated number
return self.totalReturn the final accumulated sum after traversal
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private int total = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return total;
    }
    private void dfs(TreeNode node, int currentNumber) {
        if (node == null) return;
        currentNumber = currentNumber * 10 + node.val;
        if (node.left == null && node.right == null) {
            total += currentNumber;
            return;
        }
        dfs(node.left, currentNumber);
        dfs(node.right, currentNumber);
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(3);
    //     System.out.println(new Solution().sumNumbers(root)); // 25
    // }
}
Line Notes
private int total = 0;Initialize total sum as a class member to accumulate results
public int sumNumbers(TreeNode root)Public method to start DFS and return total sum
dfs(root, 0);Start DFS with initial number 0
if (node == null) return;Base case to stop recursion on null nodes
currentNumber = currentNumber * 10 + node.val;Append current node's digit to the number
if (node.left == null && node.right == null)Check if node is leaf to add to total
total += currentNumber;Add the formed number to total sum
dfs(node.left, currentNumber);Recurse left subtree
dfs(node.right, currentNumber);Recurse right subtree
#include <iostream>
using namespace std;

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

class Solution {
    int total = 0;
public:
    void dfs(TreeNode* node, int currentNumber) {
        if (!node) return;
        currentNumber = currentNumber * 10 + node->val;
        if (!node->left && !node->right) {
            total += currentNumber;
            return;
        }
        dfs(node->left, currentNumber);
        dfs(node->right, currentNumber);
    }
    int sumNumbers(TreeNode* root) {
        total = 0;
        dfs(root, 0);
        return total;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(3);
//     Solution sol;
//     cout << sol.sumNumbers(root) << endl; // Output: 25
//     return 0;
// }
Line Notes
int total = 0;Class member to accumulate sum of all root-to-leaf numbers
void dfs(TreeNode* node, int currentNumber)DFS helper function carrying current number formed
if (!node) return;Stop recursion on null nodes
currentNumber = currentNumber * 10 + node->val;Append current node's digit to current number
if (!node->left && !node->right)Check if node is leaf to add current number to total
total += currentNumber;Add formed number to total sum
dfs(node->left, currentNumber);Recurse on left child
dfs(node->right, currentNumber);Recurse on right child
return total;Return final sum after traversal
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var sumNumbers = function(root) {
    let total = 0;
    function dfs(node, currentNumber) {
        if (!node) return;
        currentNumber = currentNumber * 10 + node.val;
        if (!node.left && !node.right) {
            total += currentNumber;
            return;
        }
        dfs(node.left, currentNumber);
        dfs(node.right, currentNumber);
    }
    dfs(root, 0);
    return total;
};

// Example usage:
// const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
// console.log(sumNumbers(root)); // 25
Line Notes
let total = 0;Initialize total sum to accumulate root-to-leaf numbers
function dfs(node, currentNumber)Recursive DFS helper carrying current number
if (!node) return;Stop recursion on null nodes
currentNumber = currentNumber * 10 + node.val;Append current node's digit to current number
if (!node.left && !node.right)Check if node is leaf to add current number to total
total += currentNumber;Add formed number to total sum
dfs(node.left, currentNumber);Recurse left subtree
dfs(node.right, currentNumber);Recurse right subtree
return total;Return final sum after traversal
⏱
Complexity
TimeO(n)
SpaceO(h)

We visit each node once, so time is O(n). The recursion stack can go as deep as the tree height h, so space is O(h).

💡 For a tree with 1000 nodes and height 10, this means about 1000 operations and stack depth 10, which is efficient.
Interview Verdict: Accepted

This approach is straightforward and efficient enough for typical interview constraints, making it a solid baseline solution.

🧠
Iterative DFS Using Stack
💡 Using an explicit stack instead of recursion helps avoid stack overflow and shows mastery of DFS traversal techniques.

Intuition

Simulate the recursive DFS with a stack that stores pairs of nodes and the current number formed so far, processing nodes iteratively.

Algorithm

  1. Initialize a stack with the root node and initial number 0.
  2. While stack is not empty, pop a node and current number.
  3. Update current number by appending node's digit.
  4. If node is leaf, add current number to total sum.
  5. Otherwise, push non-null children with updated numbers onto stack.
💡 The key is to maintain the current number alongside each node in the stack to correctly accumulate values.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root:
            return 0
        total = 0
        stack = [(root, 0)]
        while stack:
            node, current_number = stack.pop()
            current_number = current_number * 10 + node.val
            if not node.left and not node.right:
                total += current_number
            if node.right:
                stack.append((node.right, current_number))
            if node.left:
                stack.append((node.left, current_number))
        return total

# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(3))
# print(Solution().sumNumbers(root))  # Output: 25
Line Notes
if not root:Handle empty tree edge case
stack = [(root, 0)]Initialize stack with root and initial number 0
while stack:Process nodes until stack is empty
node, current_number = stack.pop()Pop node and current number from stack
current_number = current_number * 10 + node.valAppend current node's digit to current number
if not node.left and not node.right:If leaf, add current number to total
stack.append((node.right, current_number))Push right child with updated number if exists
stack.append((node.left, current_number))Push left child with updated number if exists
return totalReturn total sum after traversal
import java.util.Stack;

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

public class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        int total = 0;
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 0));
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> p = stack.pop();
            TreeNode node = p.getKey();
            int currentNumber = p.getValue() * 10 + node.val;
            if (node.left == null && node.right == null) {
                total += currentNumber;
            }
            if (node.right != null) {
                stack.push(new Pair<>(node.right, currentNumber));
            }
            if (node.left != null) {
                stack.push(new Pair<>(node.left, currentNumber));
            }
        }
        return total;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(3);
    //     System.out.println(new Solution().sumNumbers(root)); // 25
    // }
}

// Note: Pair class can be imported from javafx.util.Pair or custom implemented.
Line Notes
if (root == null) return 0;Handle empty tree edge case
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();Initialize stack to hold nodes and current numbers
stack.push(new Pair<>(root, 0));Push root with initial number 0
while (!stack.isEmpty()) {Process nodes until stack is empty
Pair<TreeNode, Integer> p = stack.pop();Pop node and current number
int currentNumber = p.getValue() * 10 + node.val;Append node's digit to current number
if (node.left == null && node.right == null)If leaf, add current number to total
stack.push(new Pair<>(node.right, currentNumber));Push right child if exists
stack.push(new Pair<>(node.left, currentNumber));Push left child if exists
return total;Return total sum after traversal
#include <iostream>
#include <stack>
using namespace std;

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

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (!root) return 0;
        int total = 0;
        stack<pair<TreeNode*, int>> stk;
        stk.push({root, 0});
        while (!stk.empty()) {
            auto [node, currentNumber] = stk.top();
            stk.pop();
            currentNumber = currentNumber * 10 + node->val;
            if (!node->left && !node->right) {
                total += currentNumber;
            }
            if (node->right) stk.push({node->right, currentNumber});
            if (node->left) stk.push({node->left, currentNumber});
        }
        return total;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(3);
//     Solution sol;
//     cout << sol.sumNumbers(root) << endl; // 25
//     return 0;
// }
Line Notes
if (!root) return 0;Handle empty tree edge case
stack<pair<TreeNode*, int>> stk;Stack holds pairs of nodes and current numbers
stk.push({root, 0});Push root with initial number 0
while (!stk.empty()) {Process nodes until stack is empty
auto [node, currentNumber] = stk.top();Pop node and current number
currentNumber = currentNumber * 10 + node->val;Append node's digit to current number
if (!node->left && !node->right)If leaf, add current number to total
stk.push({node->right, currentNumber});Push right child if exists
stk.push({node->left, currentNumber});Push left child if exists
return total;Return total sum after traversal
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var sumNumbers = function(root) {
    if (!root) return 0;
    let total = 0;
    let stack = [[root, 0]];
    while (stack.length > 0) {
        let [node, currentNumber] = stack.pop();
        currentNumber = currentNumber * 10 + node.val;
        if (!node.left && !node.right) {
            total += currentNumber;
        }
        if (node.right) stack.push([node.right, currentNumber]);
        if (node.left) stack.push([node.left, currentNumber]);
    }
    return total;
};

// Example usage:
// const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
// console.log(sumNumbers(root)); // 25
Line Notes
if (!root) return 0;Handle empty tree edge case
let stack = [[root, 0]];Initialize stack with root and initial number 0
while (stack.length > 0) {Process nodes until stack is empty
let [node, currentNumber] = stack.pop();Pop node and current number
currentNumber = currentNumber * 10 + node.val;Append node's digit to current number
if (!node.left && !node.right)If leaf, add current number to total
stack.push([node.right, currentNumber]);Push right child if exists
stack.push([node.left, currentNumber]);Push left child if exists
return total;Return total sum after traversal
⏱
Complexity
TimeO(n)
SpaceO(h)

Each node is visited once, so time is O(n). The stack holds at most h nodes, where h is tree height, so space is O(h).

💡 For a tree with 1000 nodes and height 10, this means about 1000 operations and stack size up to 10.
Interview Verdict: Accepted

This approach avoids recursion depth issues and is useful in languages with limited recursion stack.

🧠
Morris Preorder Traversal (Space Optimized)
💡 This advanced approach uses Morris traversal to do DFS without recursion or stack, reducing space to O(1). It is less common but impressive to mention in interviews.

Intuition

Use threaded binary tree traversal to visit nodes in preorder, carrying the current number along the path, and add to sum at leaves without extra space.

Algorithm

  1. Initialize current node as root and current number as 0.
  2. While current is not null, if left child is null, process current node and move right.
  3. If left child exists, find predecessor (rightmost node in left subtree).
  4. If predecessor's right is null, link it to current, update current number, and move left.
  5. If predecessor's right points to current, revert link, remove left subtree digits from current number, and move right.
  6. Add to sum when at leaf nodes.
💡 The tricky part is managing the current number as you move down and back up the tree without recursion or stack.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        total = 0
        current_number = 0
        node = root
        while node:
            if node.left is None:
                current_number = current_number * 10 + node.val
                if node.left is None and node.right is None:
                    total += current_number
                node = node.right
                current_number //= 10
            else:
                predecessor = node.left
                steps = 1
                while predecessor.right and predecessor.right != node:
                    predecessor = predecessor.right
                    steps += 1
                if predecessor.right is None:
                    predecessor.right = node
                    current_number = current_number * 10 + node.val
                    node = node.left
                else:
                    predecessor.right = None
                    if not node.left and not node.right:
                        total += current_number
                    current_number //= 10 ** steps
                    node = node.right
        return total

# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(3))
# print(Solution().sumNumbers(root))  # Output: 25
Line Notes
total = 0Initialize total sum accumulator
current_number = 0Current number formed along the path
while node:Traverse until all nodes are processed
if node.left is None:If no left child, process current node and move right
current_number = current_number * 10 + node.valAppend current node's digit
if node.left is None and node.right is None:If leaf, add current number to total
predecessor = node.leftFind predecessor in left subtree
while predecessor.right and predecessor.right != node:Find rightmost node in left subtree or threaded link
predecessor.right = nodeCreate threaded link to current node
current_number //= 10 ** stepsRemove digits added when backtracking
predecessor.right = NoneRemove threaded link to restore tree
return totalReturn final sum
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int sumNumbers(TreeNode root) {
        int total = 0;
        int currentNumber = 0;
        TreeNode node = root;
        while (node != null) {
            if (node.left == null) {
                currentNumber = currentNumber * 10 + node.val;
                if (node.left == null && node.right == null) {
                    total += currentNumber;
                }
                node = node.right;
                currentNumber /= 10;
            } else {
                TreeNode predecessor = node.left;
                int steps = 1;
                while (predecessor.right != null && predecessor.right != node) {
                    predecessor = predecessor.right;
                    steps++;
                }
                if (predecessor.right == null) {
                    predecessor.right = node;
                    currentNumber = currentNumber * 10 + node.val;
                    node = node.left;
                } else {
                    predecessor.right = null;
                    if (node.left == null && node.right == null) {
                        total += currentNumber;
                    }
                    currentNumber /= (int) Math.pow(10, steps);
                    node = node.right;
                }
            }
        }
        return total;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(3);
    //     System.out.println(new Solution().sumNumbers(root)); // 25
    // }
}
Line Notes
int total = 0;Initialize total sum accumulator
int currentNumber = 0;Current number formed along the path
while (node != null) {Traverse nodes until done
if (node.left == null) {If no left child, process current node and move right
currentNumber = currentNumber * 10 + node.val;Append current node's digit
if (node.left == null && node.right == null)If leaf, add current number to total
TreeNode predecessor = node.left;Find predecessor in left subtree
while (predecessor.right != null && predecessor.right != node)Find rightmost node or threaded link
predecessor.right = node;Create threaded link
currentNumber /= (int) Math.pow(10, steps);Remove digits when backtracking
predecessor.right = null;Remove threaded link to restore tree
return total;Return final sum
#include <iostream>
#include <cmath>
using namespace std;

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

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int total = 0;
        int currentNumber = 0;
        TreeNode* node = root;
        while (node) {
            if (!node->left) {
                currentNumber = currentNumber * 10 + node->val;
                if (!node->left && !node->right) {
                    total += currentNumber;
                }
                node = node->right;
                currentNumber /= 10;
            } else {
                TreeNode* predecessor = node->left;
                int steps = 1;
                while (predecessor->right && predecessor->right != node) {
                    predecessor = predecessor->right;
                    steps++;
                }
                if (!predecessor->right) {
                    predecessor->right = node;
                    currentNumber = currentNumber * 10 + node->val;
                    node = node->left;
                } else {
                    predecessor->right = nullptr;
                    if (!node->left && !node->right) {
                        total += currentNumber;
                    }
                    currentNumber /= (int)pow(10, steps);
                    node = node->right;
                }
            }
        }
        return total;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(3);
//     Solution sol;
//     cout << sol.sumNumbers(root) << endl; // 25
//     return 0;
// }
Line Notes
int total = 0;Initialize total sum accumulator
int currentNumber = 0;Current number formed along the path
while (node) {Traverse nodes until done
if (!node->left) {If no left child, process current node and move right
currentNumber = currentNumber * 10 + node->val;Append current node's digit
if (!node->left && !node->right)If leaf, add current number to total
TreeNode* predecessor = node->left;Find predecessor in left subtree
while (predecessor->right && predecessor->right != node)Find rightmost node or threaded link
predecessor->right = node;Create threaded link
currentNumber /= (int)pow(10, steps);Remove digits when backtracking
predecessor->right = nullptr;Remove threaded link to restore tree
return total;Return final sum
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

var sumNumbers = function(root) {
    let total = 0;
    let currentNumber = 0;
    let node = root;
    while (node !== null) {
        if (node.left === null) {
            currentNumber = currentNumber * 10 + node.val;
            if (node.left === null && node.right === null) {
                total += currentNumber;
            }
            node = node.right;
            currentNumber = Math.floor(currentNumber / 10);
        } else {
            let predecessor = node.left;
            let steps = 1;
            while (predecessor.right !== null && predecessor.right !== node) {
                predecessor = predecessor.right;
                steps++;
            }
            if (predecessor.right === null) {
                predecessor.right = node;
                currentNumber = currentNumber * 10 + node.val;
                node = node.left;
            } else {
                predecessor.right = null;
                if (node.left === null && node.right === null) {
                    total += currentNumber;
                }
                currentNumber = Math.floor(currentNumber / Math.pow(10, steps));
                node = node.right;
            }
        }
    }
    return total;
};

// Example usage:
// const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
// console.log(sumNumbers(root)); // 25
Line Notes
let total = 0;Initialize total sum accumulator
let currentNumber = 0;Current number formed along the path
while (node !== null) {Traverse nodes until done
if (node.left === null) {If no left child, process current node and move right
currentNumber = currentNumber * 10 + node.val;Append current node's digit
if (node.left === null && node.right === null)If leaf, add current number to total
let predecessor = node.left;Find predecessor in left subtree
while (predecessor.right !== null && predecessor.right !== node)Find rightmost node or threaded link
predecessor.right = node;Create threaded link
currentNumber = Math.floor(currentNumber / Math.pow(10, steps));Remove digits when backtracking
predecessor.right = null;Remove threaded link to restore tree
return total;Return final sum
⏱
Complexity
TimeO(n)
SpaceO(1)

Each node is visited a constant number of times, so time is O(n). No recursion or stack is used, so space is O(1).

💡 For 1000 nodes, this means about 1000 operations and minimal memory usage, which is optimal.
Interview Verdict: Accepted

This approach is optimal in space but more complex to implement, so mention it if time permits or interviewer asks for optimization.

📊
All Approaches - One-Glance Tradeoffs
💡 For most interviews, the recursive DFS approach is best to code quickly and clearly. Iterative DFS is good if recursion depth is a concern. Morris traversal is advanced and rarely required.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Recursive DFS)O(n)O(h)Yes (deep recursion)N/ACode this approach in 95% of interviews
2. Iterative DFS Using StackO(n)O(h)NoN/AMention or code if recursion is risky
3. Morris Preorder TraversalO(n)O(1)NoN/AMention only if asked for space optimization
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the brute force recursive DFS approach.Step 3: Discuss iterative DFS to avoid recursion stack issues.Step 4: Optionally mention Morris traversal for space optimization.Step 5: Code the chosen approach carefully and test with examples.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of DFS, carrying state along paths, handling edge cases, and coding clean recursion or iteration.

Common Follow-ups

  • What if the tree is very deep? → Use iterative DFS or Morris traversal to avoid stack overflow.
  • Can you do it without recursion or extra space? → Morris traversal is a good answer.
💡 These follow-ups check if you understand recursion limits and advanced traversal techniques.
🔍
Pattern Recognition

When to Use

Use this pattern when you need to process all root-to-leaf paths in a tree and accumulate values along the path.

Signature Phrases

'root-to-leaf path represents a number''sum of all numbers formed by root-to-leaf paths'

NOT This Pattern When

Problems that ask for maximum path sum between any two nodes (not root-to-leaf) or subtree sums are different patterns.

Similar Problems

Binary Tree Paths - similar path enumerationPath Sum - similar root-to-leaf path sum but with addition instead of number formation

Practice

(1/5)
1. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?
def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited != peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result
easy
A. [2, 3, 1]
B. [1, 3, 2]
C. [3, 2, 1]
D. [3, 1, 2]

Solution

  1. Step 1: Trace traversal on given tree

    Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.
  2. Step 2: Process nodes in postorder

    3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Output matches postorder [3, 2, 1] [OK]
Hint: Postorder output for this tree is [3,2,1] [OK]
Common Mistakes:
  • Confusing order of appending nodes
  • Off-by-one in stack popping
2. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?
easy
A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.
B. Use dynamic programming to store sums of subtrees and combine results bottom-up.
C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.
D. Use a greedy approach to prune paths that exceed the target sum early.

Solution

  1. Step 1: Understand problem constraints and path definition

    The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.
  2. Step 2: Recognize prefix sum with DFS pattern

    Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Prefix sum + DFS solves in linear time [OK]
Hint: Prefix sums track cumulative sums efficiently [OK]
Common Mistakes:
  • Assuming paths must start at root or leaf
  • Using brute force DFS from every node without pruning
  • Trying greedy pruning which fails on negative values
3. Consider this modified code snippet for the Binary Tree Cameras problem. Which line contains the subtle bug that causes incorrect camera placement?
medium
A. Line returning COVERED_NO_CAM after placing a camera instead of HAS_CAM
B. Line returning NOT_COVERED at the end of dfs
C. Line checking if dfs(root) == NOT_COVERED after traversal
D. Line returning COVERED_NO_CAM when node is null

Solution

  1. Step 1: Identify camera placement logic

    When a child is NOT_COVERED, a camera must be placed at current node and dfs must return HAS_CAM to indicate camera presence.
  2. Step 2: Locate incorrect return

    The code returns COVERED_NO_CAM after placing a camera, which falsely signals no camera here, causing parents to misinterpret coverage.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Returning HAS_CAM is essential after placing a camera [OK]
Hint: Return HAS_CAM after placing camera to signal coverage [OK]
Common Mistakes:
  • Returning COVERED_NO_CAM instead of HAS_CAM after camera placement
  • Forgetting to add camera if root uncovered
  • Mixing coverage states in conditions
4. Examine the following buggy code snippet for computing the maximum path sum in a binary tree. Which line contains the subtle bug that causes incorrect results on trees with negative node values?
def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max_gain(node.left)
        right_gain = max_gain(node.right)
        current_path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path_sum)
        # Bug: returns sum of both left and right gains to parent
        return node.val + left_gain + right_gain

    max_gain(root)
    return max_sum
medium
A. Line returning 0 for null node
B. Line computing current_path_sum = node.val + left_gain + right_gain
C. Line updating max_sum = max(max_sum, current_path_sum)
D. Line returning node.val + left_gain + right_gain

Solution

  1. Step 1: Understand return value meaning

    The function returns the maximum gain from the current node to its parent, which must be a single path (not both children).
  2. Step 2: Identify the bug

    Returning node.val + left_gain + right_gain sums both children, which is invalid for parent gain; only one child path can be extended.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Return should be node.val + max(left_gain, right_gain) [OK]
Hint: Return value must be single path gain, not sum of both children [OK]
Common Mistakes:
  • Returning sum of both children gains
  • Ignoring negative gains
  • Updating max_sum incorrectly
5. Suppose the binary tree nodes have parent pointers already, but the tree is very deep (height h). You want to find the Lowest Common Ancestor of two nodes p and q. Which approach is best to optimize time and space, and why?
hard
A. Use brute force by checking all ancestors of p and q repeatedly until common ancestor is found.
B. Use the parent pointer + ancestor set approach, building a set for p's ancestors and then traversing q's ancestors.
C. Use recursive DFS from root to find paths to p and q, then compare paths to find LCA.
D. Use the parent pointer + two-pointer technique: move the deeper node up until both nodes are at the same depth, then move both up simultaneously until they meet.

Solution

  1. Step 1: Understand problem constraints

    Nodes have parent pointers, tree is deep, so space usage matters.
  2. Step 2: Evaluate approaches

    Ancestor set approach (B) uses O(h) space. Recursive DFS (C) and brute force (D) are inefficient for deep trees.
  3. Step 3: Two-pointer technique

    Moving deeper node up to equalize depth, then moving both up simultaneously uses O(1) space and O(h) time, optimal for deep trees.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Two-pointer approach optimizes space and time for deep trees with parent pointers [OK]
Hint: Two-pointer approach uses O(1) space for LCA with parent pointers [OK]
Common Mistakes:
  • Using ancestor sets unnecessarily
  • Recursing from root wasting time
  • Brute force repeated ancestor checks
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