Sum of Root To Leaf Binary Numbers
EasyPrompt
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 = 22Example 2:
Input: root = [0]
Output: 0
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. Node.valis0or1.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a standard Depth-First Search (DFS) traversal. As we traverse from the root to a leaf, we build a string representing the binary number along that path. When a leaf node is reached, this binary string is converted to its integer equivalent, and this value is added to a running total.
Algorithm
- Initialize a global variable
totalSumto 0. - Create a recursive helper function
dfs(node, pathString)that takes the current node and the binary string representation of the path so far. - In the main function, call the helper function with the root node and an empty string:
dfs(root, ""). - Inside the
dfsfunction:- If the current node is
null, return. - Append the current node's value to
pathString. - If the current node is a leaf (both children are
null), convertpathStringto an integer from base 2 and add it tototalSum. - Recursively call
dfsfor the left and right children with the updatedpathString.
- If the current node is
- After the initial call returns,
totalSumwill hold the final result.
Walkthrough
This method is straightforward but less efficient. We traverse the tree using recursion, maintaining the current path from the root as a string of '0's and '1's.
- Initialization: We use a member variable,
totalSum, to accumulate the sum of all path numbers. - Traversal: A recursive function, say
findPathSum(node, currentPath), is used. It's initially called with therootand an empty string"". - Path Building: In each recursive call, we append the current
node.valto thecurrentPathstring. - Leaf Node Check: When we encounter a leaf node (a node where both
leftandrightchildren arenull), it signifies the end of a root-to-leaf path. At this point, thecurrentPathstring holds the complete binary representation of a number. - Conversion and Summation: We convert this binary string into an integer using
Integer.parseInt(currentPath, 2)and add the result to ourtotalSum. - Recursion: For non-leaf nodes, we continue the process by making recursive calls for the left and right children.
class Solution { int totalSum = 0; public int sumRootToLeaf(TreeNode root) { findPathSum(root, ""); return totalSum; } private void findPathSum(TreeNode node, String currentPath) { if (node == null) { return; } // Append current node's value to the path string currentPath += node.val; // If it's a leaf node, parse the binary string and add to sum if (node.left == null && node.right == null) { totalSum += Integer.parseInt(currentPath, 2); return; } // Recur for left and right children findPathSum(node.left, currentPath); findPathSum(node.right, currentPath); }}Complexity
Time
O(N * H), where N is the number of nodes and H is the height of the tree. The traversal itself visits each node once (O(N)). However, string concatenation in a loop can take O(H) time, and parsing the string at each of the L leaf nodes also takes O(H) time. This leads to a complexity that is worse than linear.
Space
O(H), where H is the height of the tree. This space is used by the recursion call stack and to store the path string. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N).
Trade-offs
Pros
The logic is very intuitive and directly follows the problem statement.
Easy to implement for those familiar with basic tree traversal.
Cons
Inefficient due to the overhead of string concatenation and parsing.
The time complexity is worse than linear, making it unsuitable for large or deep trees.
This approach achieves the same optimal time complexity as the recursive solution but uses an explicit stack to perform the DFS traversal, thus avoiding recursion. This can be beneficial for extremely deep trees where recursion might lead to a stack overflow.
Algorithm
- Initialize
totalSum = 0. - Create a stack to store pairs of
(TreeNode, currentNumber). - Push the initial pair
(root, 0)onto the stack. - Loop while the stack is not empty:
- Pop a pair
(node, pathValue). - Calculate the new path value:
newPathValue = (pathValue << 1) | node.val. - If the
nodeis a leaf, addnewPathValuetototalSum. - If the
nodehas a right child, push(node.right, newPathValue)onto the stack. - If the
nodehas a left child, push(node.left, newPathValue)onto the stack.
- Pop a pair
- Return
totalSum.
Walkthrough
Instead of recursion, we can simulate the traversal using a stack. This approach is equally efficient and avoids the limitations of the recursion depth.
- Data Structure: We use a
Stackto store pairs of(TreeNode, int). The integer in the pair will hold the numerical value of the path from the root to the node. - Initialization: We start by pushing a pair containing the
rootnode and an initial path value of0onto the stack. AtotalSumvariable is initialized to0. - Iteration: We loop as long as the stack is not empty. In each step:
- We pop a
(node, pathValue)pair. - We calculate the value for the path down to the current node using the bitwise shift-left and OR operation:
newPathValue = (pathValue << 1) | node.val. - Leaf Check: If the current node is a leaf, we've found a complete path number. We add
newPathValueto ourtotalSum. - Push Children: If the node is not a leaf, we push its children onto the stack for future processing. We push the right child first, then the left child, so that the traversal explores the left subtree before the right, mimicking a preorder traversal.
- We pop a
import java.util.Stack; // A helper class to store the node and its path sumclass Pair { TreeNode node; int sum; Pair(TreeNode node, int sum) { this.node = node; this.sum = sum; }} class Solution { public int sumRootToLeaf(TreeNode root) { if (root == null) { return 0; } int totalSum = 0; Stack<Pair> stack = new Stack<>(); stack.push(new Pair(root, 0)); while (!stack.isEmpty()) { Pair current = stack.pop(); TreeNode node = current.node; int pathValue = current.sum; // Calculate the number for the path to this node pathValue = (pathValue << 1) | node.val; // If it's a leaf, add the path's number to the total sum if (node.left == null && node.right == null) { totalSum += pathValue; } // Push children onto the stack if they exist if (node.right != null) { stack.push(new Pair(node.right, pathValue)); } if (node.left != null) { stack.push(new Pair(node.left, pathValue)); } } return totalSum; }}Complexity
Time
O(N), where N is the number of nodes. Each node is pushed onto and popped from the stack exactly once. All operations inside the loop are constant time.
Space
O(H), where H is the height of the tree. The space is used by the stack. In the worst case of a skewed tree, the stack can hold up to H (or N) nodes, resulting in O(N) space.
Trade-offs
Pros
Optimal O(N) time complexity.
Avoids recursion, preventing potential stack overflow errors on very deep trees.
Maintains efficiency by calculating path sums numerically.
Cons
The code can be slightly more verbose than the recursive equivalent.
Requires managing an explicit stack and a helper class or pair object.
This is a highly efficient and elegant approach that avoids the overhead of string manipulation. Instead of building a string, we calculate the decimal value of the path number on the fly using bitwise operations as we traverse the tree recursively.
Algorithm
- Define a recursive helper function
dfs(node, currentNumber). - The main function should call and return the result of
dfs(root, 0). - Inside
dfs(node, currentNumber):- If
nodeisnull, return 0 (base case for non-existent children). - Calculate the new number for the path including the current node:
newNumber = (currentNumber << 1) | node.val. - If the
nodeis a leaf, returnnewNumberas it's a complete path number. - Otherwise, return the sum of the results from the recursive calls on the left and right children:
dfs(node.left, newNumber) + dfs(node.right, newNumber).
- If
Walkthrough
This optimal solution uses a preorder traversal (a type of DFS) and passes the calculated integer value of the path down through the recursive calls.
-
The Core Idea: The key is to update the path's numerical value at each step. If a path from the root to a parent node has a value of
X, and we move to a child node with valuev(which is 0 or 1), the new path's value isX * 2 + v. This operation is efficiently performed using bitwise operations:(X << 1) | v. The left shift<< 1is equivalent to multiplying by 2, and the bitwise OR| vadds the new bit (0 or 1) to the end. -
Recursive Function: We define a helper function,
dfs(TreeNode node, int currentNumber), which returns the sum of all leaf paths in the subtree rooted atnode.- Base Case: If
nodeisnull, it contributes nothing to the sum, so we return0. - Path Update: We calculate the value for the path ending at the current node:
currentNumber = (currentNumber << 1) | node.val. - Leaf Node: If the current node is a leaf (
node.left == null && node.right == null), we have found a complete path. We return its value,currentNumber. - Internal Node: If it's an internal node, the total sum from this point downwards is the sum of the paths in its left subtree and its right subtree. We find this by returning
dfs(node.left, currentNumber) + dfs(node.right, currentNumber).
- Base Case: If
-
Initial Call: The process is started by calling
dfs(root, 0)from the main function.
class Solution { public int sumRootToLeaf(TreeNode root) { return dfs(root, 0); } private int dfs(TreeNode node, int currentNumber) { if (node == null) { return 0; } // Update the current number with the new bit from the current node. currentNumber = (currentNumber << 1) | node.val; // If it's a leaf node, we have a complete path number. if (node.left == null && node.right == null) { return currentNumber; } // Otherwise, return the sum of paths from left and right children. return dfs(node.left, currentNumber) + dfs(node.right, currentNumber); }}Complexity
Time
O(N), where N is the number of nodes in the tree. We visit each node exactly once, and the work done at each node (bit shifting, ORing, addition) is constant time.
Space
O(H), where H is the height of the tree. This space is consumed by the recursion call stack. For a balanced tree, this is O(log N), and for a skewed tree, it is O(N).
Trade-offs
Pros
Optimal O(N) time complexity.
Very concise and elegant code.
Efficiently calculates the sum using fast bitwise operations.
Cons
For extremely deep trees (not an issue given the problem constraints), recursion can lead to a stack overflow error.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int sumRootToLeaf ( TreeNode root ) { return dfs ( root , 0 ); } private int dfs ( TreeNode root , int t ) { if ( root == null ) { return 0 ; } t = ( t << 1 ) | root . val ; if ( root . left == null && root . right == null ) { return t ; } return dfs ( root . left , t ) + dfs ( root . right , t ); } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int sumRootToLeaf ( TreeNode * root ) { return dfs ( root , 0 ); } int dfs ( TreeNode * root , int t ) { if ( ! root ) return 0 ; t = ( t << 1 ) | root -> val ; if ( ! root -> left && ! root -> right ) return t ; return dfs ( root -> left , t ) + dfs ( root -> right , t ); } };# Definition for a binary tree node. # 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 : def dfs ( root , t ): if root is None : return 0 t = ( t << 1 ) | root . val if root . left is None and root . right is None : return t return dfs ( root . left , t ) + dfs ( root . right , t ) return dfs ( root , 0 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.