Sum of Root To Leaf Binary Numbers solution and explanation
Google
9 more videos on this problem
Sum of Root To Leaf Binary Numbers | LeetCode 1022 | C++, Java, PythonKnowledge Center · 15:00 · 9K views
Leetcode - Sum of Root To Leaf Binary Numbers (Python)Timothy H Chang · 4:53 · 1K views
Sum of Root To Leaf Binary Numbers | Leet code 1022 | Theory explained + Python codeSai Anish Malla · 13:21 · 1K views
Sum of Root To Leaf Binary Numbers | Leetcode 1022 | Live coding session 🔥🔥| Basic Tree Traversal 💯Coding Decoded · 6:55 · 982 views
1022. Sum of Root To Leaf Binary Numbers | Leetcode Daily - PythonLeetcode Daily · 7:01 · 710 views
Sum of Root To Leaf Binary Numbers | Leetcode 1022 | Leetcode September challengeCode Bashers · 9:24 · 681 views
1022. Sum of Root To Leaf Binary Numbers (Leetcode Easy)Programming Live with Larry · 13:31 · 595 views
Daily Leetcode #2156: Feb 24, 2026 - 1022. Sum of Root To Leaf Binary NumbersProgramming Live with Larry · 3:24 · 420 views
LeetCode 1022. [easy] Sum of Root To Leaf Binary NumbersFrancesco Manicardi · 4:08 · 192 views
Sum of Root To Leaf Binary Numbers | LeetCode 1022 | Recursive approach | Interview questionsFaxMachine Codes · 8:44 · 163 views
The problem
You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.
- For example, if the path is
0 -> 1 -> 1 -> 0 -> 1, then this could represent01101in binary, which is13.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.
The test cases are generated so that the answer fits in a 32-bits integer.
Example 1:
Input: root = [1,0,1,0,1,0,1] Output: 22 Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
Example 2:
Input: root = [0] Output: 0
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. Node.valis0or1.
Approach overview
Problem Overview: Each root-to-leaf path in the binary tree represents a binary number where every node contributes a bit (0 or 1). Moving from the root to a leaf builds a binary sequence. Convert each path into its decimal value and return the sum of all such numbers.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
This approach traverses the tree using recursion. As you move down a path, maintain the current binary value formed so far. At each node, shift the accumulated value left by one bit (current << 1) and add the node’s value using a bitwise OR or addition. When a leaf node is reached, the accumulated value represents a full binary number, so add it to the total sum.
The key insight: binary digits are built incrementally as you traverse the path. Shifting left is equivalent to multiplying by 2, which matches how binary numbers grow when a new bit is appended. Every node is processed exactly once, making the time complexity O(n) where n is the number of nodes. Recursion depth depends on the tree height, so space complexity is O(h). This method naturally fits problems involving path-based computations in tree structures and is the cleanest implementation using Depth-First Search.
Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))
The iterative version replaces recursion with an explicit stack. Each stack entry stores a pair: the current node and the binary value built along the path to that node. Pop a node from the stack, update the binary value using the same shift operation (value = (value << 1) | node.val), and check whether it is a leaf. If it is, add the value to the total sum. Otherwise, push its children onto the stack with the updated value.
This approach performs the same logical steps as recursive DFS but avoids relying on the call stack. It is useful in environments where recursion depth might be limited or when you want explicit control over traversal order. Time complexity remains O(n) since each node is visited once, and the stack holds at most O(h) nodes at a time in a balanced binary tree.
Recommended for interviews: Recursive DFS is typically expected because the code is concise and directly mirrors the tree structure. Interviewers look for the insight that the path forms a binary number and can be built incrementally using a left shift operation. Implementing the iterative stack version demonstrates deeper understanding of DFS mechanics and control over recursion.
Approach 1: Recursive Depth-First Search (DFS)
This approach involves using a recursive function to traverse the binary tree from the root to the leaves. During the traversal, we calculate the binary number formed by the path from the root to the current node, then sum up the numbers obtained when a leaf node is reached. The traversal is achieved using depth-first search (DFS).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
return self.calculateSum(root, 0)
def calculateSum(self, node: TreeNode, currentSum: int) -> int:
if not node:
return 0
currentSum = (currentSum << 1) | node.val
if not node.left and not node.right:
return currentSum
return self.calculateSum(node.left, currentSum) + self.calculateSum(node.right, currentSum)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int sumRootToLeaf(TreeNode root) {
return calculateSum(root, 0);
}
private int calculateSum(TreeNode node, int currentSum) {
if (node == null) {
return 0;
}
currentSum = (currentSum << 1) | node.val;
if (node.left == null && node.right == null) {
return currentSum;
}
return calculateSum(node.left, currentSum) + calculateSum(node.right, currentSum);
}
}#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int sumRootToLeaf(TreeNode* root, int currentSum = 0) {
if (!root) return 0;
currentSum = (currentSum << 1) | root->val;
if (!root->left && !root->right) return currentSum;
return sumRootToLeaf(root->left, currentSum) + sumRootToLeaf(root->right, currentSum);
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var sumRootToLeaf = function(root) {
return calculateSum(root, 0);
};
function calculateSum(node, currentSum) {
if (node === null) return 0;
currentSum = (currentSum << 1) | node.val;
if (node.left === null && node.right === null) return currentSum;
return calculateSum(node.left, currentSum) + calculateSum(node.right, currentSum);
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int calculateSum(struct TreeNode* root, int currentSum) {
if (root == NULL) {
return 0;
}
currentSum = (currentSum << 1) | root->val;
if (root->left == NULL && root->right == NULL) {
return currentSum;
}
return calculateSum(root->left, currentSum) + calculateSum(root->right, currentSum);
}
int sumRootToLeaf(struct TreeNode* root) {
return calculateSum(root, 0);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int SumRootToLeaf(TreeNode root) {
return CalculateSum(root, 0);
}
private int CalculateSum(TreeNode node, int currentSum) {
if (node == null) return 0;
currentSum = (currentSum << 1) | node.val;
if (node.left == null && node.right == null) return currentSum;
return CalculateSum(node.left, currentSum) + CalculateSum(node.right, currentSum);
}
}This Python implementation involves recursively traversing a binary tree and computing binary sums as decimal for each root-to-leaf path. We accumulate these sums to achieve the final result.
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(h), affected by the recursion depth, h.
Approach 2: Iterative Depth-First Search (DFS) with Stack
This approach utilizes an iterative technique employing a stack to carry out a DFS. In each iteration, nodes are retrieved alongside their corresponding computed binary sum. This method is advantageous when stack overflow due to recursion is a concern, as it emulates recursion iteratively.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
stack = [(root, 0)]
total_sum = 0
while stack:
node, current_sum = stack.pop()
if node:
current_sum = (current_sum << 1) | node.val
if not node.left and not node.right:
total_sum += current_sum
else:
stack.append((node.right, current_sum))
stack.append((node.left, current_sum))
return total_sumimport java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int sumRootToLeaf(TreeNode root) {
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
stack.push(new Pair<>(root, 0));
int sum = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> pair = stack.pop();
TreeNode node = pair.getKey();
int currentSum = pair.getValue();
if (node != null) {
currentSum = (currentSum << 1) | node.val;
if (node.left == null && node.right == null) {
sum += currentSum;
} else {
stack.push(new Pair<>(node.right, currentSum));
stack.push(new Pair<>(node.left, currentSum));
}
}
}
return sum;
}
}function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var sumRootToLeaf = function(root) {
let stack = [[root, 0]];
let sum = 0;
while (stack.length > 0) {
let [node, currentSum] = stack.pop();
if (node !== null) {
currentSum = (currentSum << 1) | node.val;
if (!node.left && !node.right) {
sum += currentSum;
} else {
stack.push([node.right, currentSum]);
stack.push([node.left, currentSum]);
}
}
}
return sum;
};This Python implementation leverages a stack to perform iterative DFS. A tuple tracks each node alongside the current binary sum being accumulated. The process ensures all leaf nodes' paths are accounted for, computing a total sum iteratively.
Time Complexity: O(n), resulting from single-pass node visits.
Space Complexity: O(n), relevant to the stack's use for storing node sequences.
Approach 3: Recursion
We design a recursive function dfs(root, t), which takes two parameters: the current node root and the binary number t corresponding to the parent node of the current node. The return value of the function is the sum of binary numbers represented by paths from the current node to leaf nodes. The answer is \textrm{dfs}(root, 0).
The logic of the recursive function is as follows:
- If the current node
rootis null, return0; otherwise, calculate the binary numbertcorresponding to the current node, i.e.,t = t \ll 1 | root.val. - If the current node is a leaf node, return
t; otherwise, return the sum of\textrm{dfs}(root.left, t)and\textrm{dfs}(root.right, t).
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited once; the recursion stack requires O(n) space.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function sumRootToLeaf(root: TreeNode | null): number {
const dfs = (node: TreeNode | null, x: number): number => {
if (node === null) {
return 0;
}
x = (x << 1) | node.val;
if (node.left === null && node.right === null) {
return x;
}
return dfs(node.left, x) + dfs(node.right, x);
};
return dfs(root, 0);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumRootToLeaf(root *TreeNode) int {
var dfs func(*TreeNode, int) int
dfs = func(root *TreeNode, x int) int {
if root == nil {
return 0
}
x = x<<1 | root.Val
if root.Left == root.Right {
return x
}
return dfs(root.Left, x) + dfs(root.Right, x)
}
return dfs(root, 0)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn sum_root_to_leaf(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn dfs(node: Option<Rc<RefCell<TreeNode>>>, x: i32) -> i32 {
if let Some(n) = node {
let n_ref = n.borrow();
let x = (x << 1) | n_ref.val;
if n_ref.left.is_none() && n_ref.right.is_none() {
return x;
}
dfs(n_ref.left.clone(), x) + dfs(n_ref.right.clone(), x)
} else {
0
}
}
dfs(root, 0)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes. |
| Iterative Depth-First Search (DFS) with Stack | Time Complexity: O(n), resulting from single-pass node visits. |
| Recursion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Best general solution. Clean and intuitive for tree traversal problems. |
| Iterative DFS with Stack | O(n) | O(h) | Useful when avoiding recursion or when stack-based traversal control is preferred. |
Frequently asked questions
Is Sum of Root To Leaf Binary Numbers easy or hard?
This problem is classified as Easy. The main challenge is recognizing that each root-to-leaf path forms a binary number and can be built incrementally using bit shifts during DFS traversal. Once that insight is clear, the implementation is straightforward.
Sum of Root To Leaf Binary Numbers Python/Java solution
Both Python and Java implementations use DFS traversal. Maintain an integer representing the current binary number and update it using a left shift and addition at each node. When reaching a leaf, add the value to the total sum. The logic runs in O(n) time and O(h) space.
How to solve Sum of Root To Leaf Binary Numbers in O(n)?
Traverse the tree using DFS while maintaining the binary value formed along the path. At each node, compute the new value using (current << 1) | node.val. When a leaf node is reached, add the computed number to the result. Since every node is visited once, the algorithm runs in O(n) time.
What is the best approach for Sum of Root To Leaf Binary Numbers?
Depth-First Search (DFS) with incremental binary construction is the most efficient approach. While traversing from root to leaf, shift the current value left by one bit and add the node’s bit. Each node is processed once, giving O(n) time complexity and O(h) space from recursion depth.
Is Sum of Root To Leaf Binary Numbers asked at Google/Amazon/Meta?
Tree traversal and DFS path problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variations involving root-to-leaf paths, path sums, or binary interpretation are common in coding interviews focused on tree algorithms.
What data structure is used in Sum of Root To Leaf Binary Numbers?
The core data structure is a binary tree. The algorithm uses Depth-First Search traversal implemented either through recursion (call stack) or an explicit stack for iterative DFS. Bit manipulation is used to efficiently build binary numbers along each path.
What is the time complexity of Sum of Root To Leaf Binary Numbers?
The time complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once during the DFS traversal. Space complexity is O(h), where h is the height of the tree due to recursion stack or the explicit stack in the iterative solution.