Sum Root to Leaf Numbers

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive DFS)	O(n)	O(h)	Yes (deep recursion)	N/A	Code this approach in 95% of interviews
2. Iterative DFS Using Stack	O(n)	O(h)	No	N/A	Mention or code if recursion is risky
3. Morris Preorder Traversal	O(n)	O(1)	No	N/A	Mention 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. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?

easy

A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.

B. Apply dynamic programming with memoization on node pairs to find longest paths.

C. Use a greedy traversal that always chooses the deeper subtree at each node.

D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

   The diameter can be found by checking the sum of left and right subtree heights at every node.

2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

   This approach visits each node once, updating the diameter with left_height + right_height.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Postorder traversal with global diameter update covers all nodes [OK]

Hint: Diameter updates at every node, not just root [OK]

Common Mistakes:

• Thinking diameter must pass through root
• Using greedy to pick deeper subtree only
• Confusing diameter with twice height

2. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

easy

A. True

B. False

C. Raises an exception due to null pointer

D. Returns True only if the root value equals targetSum

Solution

1. Step 1: Trace the path sums

   Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.

2. Step 2: Confirm code logic

   The DFS returns True as soon as it finds the matching path sum at a leaf node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Path 5↔4↔11↔2 sums to 22, so return True [OK]

Hint: Check all root-to-leaf paths, not just partial sums [OK]

Common Mistakes:

• Stopping at non-leaf nodes
• Ignoring leaf node condition

3. The following BFS-based code attempts to compute the maximum depth of a binary tree. Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input.

from collections import deque

def maxDepth(root):
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

medium

A. Line 7: Using len(queue) to determine level size

B. Line 15: Incrementing depth after processing each level

C. Line 10: Popping node from queue without null check

D. Line 2: Initializing queue with root without checking if root is null

Solution

1. Step 1: Check handling of empty tree

   Code initializes queue with root without checking if root is null, so if root is null, queue contains null, causing errors.

2. Step 2: Verify other lines

   len(queue) and popping nodes are correct if queue is valid; depth increment is necessary after each level.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing root null check causes failure on empty tree [OK]

Hint: Always check for null root before queue initialization [OK]

Common Mistakes:

• Not handling empty tree input
• Assuming root always exists
• Incrementing depth incorrectly

4. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?

hard

A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting

B. Use recursion on parent pointers to simulate traversal

C. Iteratively traverse using parent pointers and a stack to track visited nodes

D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

1. Step 1: Understand traversal constraints

   Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.

2. Step 2: Identify correct approach

   Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modified iterative approach handles parent-only trees without extra space [OK]

Hint: Parent-only trees require tracking visited nodes iteratively [OK]

Common Mistakes:

• Trying to use recursion without child pointers
• Attempting Morris traversal on parent pointers
• Using stack without tracking visited nodes

5. If the problem is modified so that the postorder traversal may contain duplicate values, which of the following changes is necessary to correctly reconstruct the tree?

hard

A. Modify the algorithm to store indices of all occurrences of each value in inorder and track usage to avoid ambiguity.

B. Use a hash map from value to index in inorder traversal as before, ignoring duplicates.

C. Switch to preorder and inorder traversals which do not have duplicates.

D. Use a greedy approach attaching nodes as left children to handle duplicates.

Solution

1. Step 1: Understand the impact of duplicates

   Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.

2. Step 2: Required modification

   Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.

3. Step 3: Why other options fail

   Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value is necessary for duplicates [OK]

Hint: Duplicates require tracking all indices, not just one [OK]

Common Mistakes:

• Ignoring duplicates in hash map
• Assuming unique values always
• Switching traversal types incorrectly