# Calculate the Sum of Root To Leaf Binary Numbers in Java

## The challenge

Given a binary tree, each node has value “ 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.

**Example 1:**

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

**Note:**

- The number of nodes in the tree is between
`1`

and`1000`

. - node.val is “ or
`1`

. - The answer will not exceed
`2^31 - 1`

.

## Given the Binary Tree definition

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

## The solution in Java

Option 1:

```
class Solution {
public int sumRootToLeaf(TreeNode root) {
int rootToLeaf = 0;
int currNumber = 0;
Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque();
stack.push(new Pair(root, 0));
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> p = stack.pop();
root = p.getKey();
currNumber = p.getValue();
if (root != null) {
currNumber = (currNumber << 1) | root.val;
if (root.left == null && root.right == null) {
rootToLeaf += currNumber;
} else {
stack.push(new Pair(root.right, currNumber));
stack.push(new Pair(root.left, currNumber));
}
}
}
return rootToLeaf;
}
}
```

Option 2 (using `Depth First Search`

):

```
class Solution {
public int sumRootToLeaf(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int sum) {
if(root == null)
return 0;
sum = sum * 2 + root.val; // sum = (sum << 1) + root.val;
return (root.left == null && root.right == null) ? sum : dfs(root.left, sum) + dfs(root.right, sum);
}
}
```

Option 3 (using `iterative`

):

```
class Solution {
int val = 0;
public int sumRootToLeaf(TreeNode root) {
Solution s = new Solution();
s.findCount(root, 0);
return s.val;
}
public void findCount(TreeNode root, int value){
if(root!=null){
int sum = root.val + value*2;
if(root.left == null && root.right == null){
this.val = this.val + sum;
}
findCount(root.left, sum);
findCount(root.right, sum);
}
}
}
```