Definition
- Running number – as you descend, compute
running = running * 10 + node.digit, building the multi-digit value top to bottom. - Leaf completion – at each leaf the running number is the full path number; return it to be summed.
- Internal node – return
dfs(left, running) + dfs(right, running); a null child contributes zero. - Complexity – O(n) time visiting each node once; O(h) space for the recursion stack, where h is the tree height.
At National Bank of India, a tree of routing desks holds one digit of an account-routing number per desk. Every path from the top desk to a bottom desk spells out one complete routing number. Rajesh walks down each path, building the number digit by digit, and at the bottom drops the finished number into a running total.
Understanding the Concepts
What is the problem?
Each node in a binary tree holds a single digit (0-9). Each root-to-leaf path forms a number by concatenating the digits. Find the sum of all such path numbers.
Example: A tree with root 1, left child 2, right child 3 forms paths 1-2 (number 12) and 1-3 (number 13). The total is 12 + 13 = 25.
How does the running-number technique work?
Each time you move to a child, shift the accumulated number one decimal place left and add the child's digit: running = running * 10 + node.digit. This naturally builds the correct multi-digit value because the root is the most significant digit and the leaf the least.
package com.bank.service;
public class PathNumberSum {
static class TreeNode {
int digit;
TreeNode left, right;
TreeNode(int digit) { this.digit = digit; }
}
public static long sumPathNumbers(TreeNode root) {
return dfs(root, 0);
}
private static long dfs(TreeNode node, long running) {
if (node == null) return 0;
running = running * 10 + node.digit;
if (node.left == null && node.right == null) {
return running; // leaf: number is complete
}
return dfs(node.left, running) + dfs(node.right, running);
}
public static void main(String[] args) {
// Routing tree at National Bank of India
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// Paths: 1-2-4=124, 1-2-5=125, 1-3=13
System.out.println("Sum of path numbers: " + sumPathNumbers(root));
}
}
Sum of path numbers: 262
Why use long instead of int?
A tree with 10 levels can produce a 10-digit number, which exceeds Integer.MAX_VALUE (about 2.1 billion). Using long accommodates paths up to 18 digits. For even longer paths, use BigInteger.
What are edge cases?
- Single-node tree: the root is itself a leaf, so the path number is just the root's digit.
- Tree where all paths go left: one very long number.
- Nodes with digit 0: contributes zeros, e.g., path 1-0-3 = 103, not 13.
// Single node: digit 5
TreeNode single = new TreeNode(5);
System.out.println(sumPathNumbers(single)); // 5
// Path with zero: 1 -> 0 -> 3 = 103
TreeNode r = new TreeNode(1);
r.left = new TreeNode(0);
r.left.left = new TreeNode(3);
System.out.println(sumPathNumbers(r)); // 103
What are common mistakes?
// Wrong: treating null as a leaf
private static long dfsBroken(TreeNode node, long running) {
if (node == null) return running; // counts every null as a path!
running = running * 10 + node.digit;
return dfsBroken(node.left, running) + dfsBroken(node.right, running);
}
// A node with one child would double-count its path
// Correct: check both children null for leaf
if (node.left == null && node.right == null) return running;
Can you solve it iteratively?
Yes, using a stack that stores (node, running) pairs.
public static long sumPathNumbersIterative(TreeNode root) {
if (root == null) return 0;
long total = 0;
Deque<long[]> stack = new ArrayDeque<>();
// stack entries: [node reference index, running number]
// For simplicity, use a stack of Object[]{node, running}
Deque<Object[]> s = new ArrayDeque<>();
s.push(new Object[]{root, 0L});
while (!s.isEmpty()) {
Object[] top = s.pop();
TreeNode node = (TreeNode) top[0];
long running = (long) top[1];
running = running * 10 + node.digit;
if (node.left == null && node.right == null) {
total += running;
} else {
if (node.right != null) s.push(new Object[]{node.right, running});
if (node.left != null) s.push(new Object[]{node.left, running});
}
}
return total;
}
What should a senior engineer know?
The running-number technique is a special case of carrying state down a DFS path. The same pattern applies to constructing strings, accumulating sums, or tracking constraints along a path. The key insight is that the state is passed as a parameter, not as a global variable, which keeps the recursion clean and thread-safe.
What are common interview follow-up questions?
- How would you handle a tree where each node holds a character instead of a digit?
- What if you need to return the path with the largest number, not the sum?
- Can you solve this with BFS?
Visual Overview
1
/ \
2 3
/ \
4 5
Path 1-2-4: running = 0→1→12→124
Path 1-2-5: running = 0→1→12→125
Path 1-3: running = 0→1→13
Total: 124 + 125 + 13 = 262
Key Takeaway
Sum of Path Numbers treats each root-to-leaf path as a multi-digit decimal number built from the single digit at each node, and asks for the total of all such numbers. The solution is a DFS that carries a running number: at every child, shift left by multiplying by ten and add the digit. The root contributes the most significant digit and the leaf the least, so the number assembles correctly top to bottom. At each leaf, return the completed number; internal nodes return the sum of their children.
The nuance is overflow. On a deep tree the concatenated value can exceed a 32-bit integer, so use a long or BigInteger to keep the total exact. Also ensure a single-node tree is handled correctly, because the root is itself a leaf and its digit is the entire number.
The most common bug is treating null as a leaf. If you return the running value at null instead of checking both-children-null, a node with one child double-counts its path. The correct leaf check is node.left == null && node.right == null.
In a banking project at National Bank of India, a routing tree held one digit per desk, and operations needed the arithmetic sum of every complete routing number for a reconciliation cross-check. The running value was carried as a long to avoid silent overflow, and the exact total was used for verification.
Remember one sentence: carry a running number with running * 10 + digit down each path and add it to the total at every leaf.
---