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. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?

easy

A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.

B. Perform a level-order traversal and compare nodes at each level from left to right.

C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.

D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

1. Step 1: Understand the problem requires mirrored subtree comparison

   The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

   The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mirrored recursive DFS matches problem requirements [OK]

Hint: Symmetry requires mirrored subtree comparison [OK]

Common Mistakes:

• Assuming preorder traversal palindrome check works
• Using level-order traversal without mirrored comparison
• Trying brute force subtree permutations

2. What is the time complexity of the brute force recursive approach that computes the diameter of a binary tree by calculating the height at each node separately?

medium

A. O(n log n)

B. O(n)

C. O(n^2)

D. O(n^3)

Solution

1. Step 1: Analyze the height function calls.

   Height is called for each node, and each call traverses its subtree, leading to repeated traversals.

2. Step 2: Calculate total complexity.

   For each of the n nodes, height is computed which can take O(n) in worst case, resulting in O(n^2) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Repeated height computations cause quadratic time [OK]

Hint: Repeated height calls cause O(n^2) time, not O(n) [OK]

Common Mistakes:

• Assuming height calls are O(1)
• Confusing recursion stack space with time
• Thinking it's O(n log n) due to balanced tree

3. The following code attempts to flatten a binary tree to a linked list in-place. Identify the bug that causes the flattened list to still have left child pointers, violating the problem requirements.

medium

A. Missing line to set root.left = None

B. Line: flatten(root.left)

C. Line: root.right = prev

D. Line: flatten(root.right)

Solution

1. Step 1: Review rewiring steps

   The code sets root.right = prev but does not set root.left = None, so left pointers remain.

2. Step 2: Identify missing step

   Setting root.left = None is required to ensure the flattened list has no left children.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Left pointers must be nullified to meet problem constraints [OK]

Hint: Always set root.left = None when flattening [OK]

Common Mistakes:

• Forgetting to nullify left pointers
• Misordering recursive calls causing wrong sequence
• Losing subtree references by incorrect rewiring

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

5. Suppose the binary tree nodes can have duplicate values, and you are given preorder and inorder traversals with duplicates. Which modification to the standard iterative approach is necessary to correctly reconstruct the tree?

hard

A. Use a hash map from value to a list of all indices in inorder, and track which index to use next during construction.

B. Ignore duplicates and build the tree as usual, since preorder and inorder uniquely identify the tree.

C. Sort the preorder array to remove duplicates before building the tree.

D. Use a brute force approach with array slicing to handle duplicates correctly.

Solution

1. Step 1: Understand the problem with duplicates

   Duplicates cause ambiguity in mapping values to inorder indices, breaking the unique root index lookup.

2. Step 2: Modify data structure

   Store all indices of each value in a list, and track which occurrence to use next to maintain correct subtree boundaries.

3. Step 3: Avoid naive approaches

   Ignoring duplicates or sorting breaks traversal properties; brute force is inefficient and unnecessary with proper tracking.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value resolves duplicate ambiguity [OK]

Hint: Track all inorder indices per value to handle duplicates [OK]

Common Mistakes:

• Assuming unique values always
• Sorting preorder breaks tree structure
• Using brute force causes inefficiency