Scale Engineer

Sum of Root To Leaf Binary Numbers

Easy
#0976Time: 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).
Algorithms
Depth-First Search
Data structures
TreeBinary Tree

Prompt

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 represent 01101 in binary, which is 13.

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.val is 0 or 1.

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 totalSum to 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 dfs function:
    • 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), convert pathString to an integer from base 2 and add it to totalSum.
    • Recursively call dfs for the left and right children with the updated pathString.
  • After the initial call returns, totalSum will 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.

  1. Initialization: We use a member variable, totalSum, to accumulate the sum of all path numbers.
  2. Traversal: A recursive function, say findPathSum(node, currentPath), is used. It's initially called with the root and an empty string "".
  3. Path Building: In each recursive call, we append the current node.val to the currentPath string.
  4. Leaf Node Check: When we encounter a leaf node (a node where both left and right children are null), it signifies the end of a root-to-leaf path. At this point, the currentPath string holds the complete binary representation of a number.
  5. Conversion and Summation: We convert this binary string into an integer using Integer.parseInt(currentPath, 2) and add the result to our totalSum.
  6. 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.

Solutions

/** * 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 ); } }

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.

← Previous

Previous problem

Next →

Next problem