# Sum of Root To Leaf Binary Numbers
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-root-to-leaf-binary-numbers
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## 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 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:**

![](https://assets.glich.co/dsa/sum-of-root-to-leaf-binary-numbers/image0.png) 

**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
## DFS with String Conversion
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.
**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).
**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.
### Explanation
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.

```java
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);
    }
}
```
### 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.

## Iterative DFS with Path Number Calculation
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.
**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.
**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.
### Explanation
Instead of recursion, we can simulate the traversal using a stack. This approach is equally efficient and avoids the limitations of the recursion depth.

1.  **Data Structure**: We use a `Stack` to store pairs of `(TreeNode, int)`. The integer in the pair will hold the numerical value of the path from the root to the node.
2.  **Initialization**: We start by pushing a pair containing the `root` node and an initial path value of `0` onto the stack. A `totalSum` variable is initialized to `0`.
3.  **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 `newPathValue` to our `totalSum`.
    - **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.

```java
import java.util.Stack;

// A helper class to store the node and its path sum
class 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;
    }
}
```
### 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 `node` is a leaf, add `newPathValue` to `totalSum`.
  - If the `node` has a right child, push `(node.right, newPathValue)` onto the stack.
  - If the `node` has a left child, push `(node.left, newPathValue)` onto the stack.
- Return `totalSum`.

## Recursive DFS with Path Number Calculation
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.
**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).
**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.
### Explanation
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.

1.  **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 value `v` (which is 0 or 1), the new path's value is `X * 2 + v`. This operation is efficiently performed using bitwise operations: `(X << 1) | v`. The left shift `<< 1` is equivalent to multiplying by 2, and the bitwise OR `| v` adds the new bit (0 or 1) to the end.

2.  **Recursive Function**: We define a helper function, `dfs(TreeNode node, int currentNumber)`, which returns the sum of all leaf paths in the subtree rooted at `node`.
    - **Base Case**: If `node` is `null`, it contributes nothing to the sum, so we return `0`.
    - **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)`.

3.  **Initial Call**: The process is started by calling `dfs(root, 0)` from the main function.

```java
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);
    }
}
```
### 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 `node` is `null`, 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 `node` is a leaf, return `newNumber` as 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)`.

# Solutions
### Java

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

### CPP

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

### Python

```python
# 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 )
```