# LeetCode: 1022. Sum of Root To Leaf Binary Numbers

**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 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**

```
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
```

**Constraints:**

- The number of nodes in the tree is in the range
`[1, 1000]`

. `Node.val`

is`0`

or`1`

.

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
int sumRootToLeaf(TreeNode* root) {
int ans = 0;
sumRootToLeaf(root, ans, 0);
return ans;
}
void sumRootToLeaf(TreeNode* root, int &sum, int prev) {
if (root == nullptr) return;
int current = (prev << 1) + root->val;
if(root->left == nullptr && root->right == nullptr)
sum += current;
else {
sumRootToLeaf(root->left, sum, current);
sumRootToLeaf(root->right, sum, current);
}
}
```

Let's break down the code step by step:

The `sumRootToLeaf`

function is defined to calculate the sum of binary numbers along root-to-leaf paths in a binary tree. It takes three parameters:

`TreeNode* root`

: A pointer to the current node being processed.`int &sum`

: A reference to the sum that will be updated throughout the traversal.`int prev`

: The binary number represented by the path from the root to the current node's parent.

Inside the `sumRootToLeaf`

function:

- The base case is checked: if
`root`

is`nullptr`

, the function returns immediately. - The binary value for the current node is calculated using bitwise operations. It takes the previous value (
`prev`

), shifts it to the left by one position (effectively multiplying by 2), and adds the value of the current node (`root->val`

). This step represents appending the current node's value to the binary number represented by the path from the root to the parent node.

- An
`if`

condition checks if the current node is a leaf node (both left and right children are`nullptr`

). If it is a leaf, the value represented by the current path (`current`

) is added to the`sum`

. This is because the current path forms a complete binary number from root to leaf, and the goal is to accumulate the sum of these numbers.

If the current node is not a leaf, the `else`

block is executed:

- The function is recursively called for the left child, passing in the updated sum, the current value, and the left child as the new root.
- The function is also recursively called for the right child in a similar manner.

Finally, the main function `int sumRootToLeaf(TreeNode* root)`

initializes the process:

- It declares an integer
`ans`

to store the final sum. - It calls the
`sumRootToLeaf`

function with the root node, the`ans`

variable, and an initial value of 0 (since there is no previous value when starting from the root). - After the traversal, it returns the calculated sum.