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

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

Example 1:

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

Note:

1. The number of nodes in the tree is between `1` and `1000`.
2. node.val is `0` or `1`.
3. The answer will not exceed `2^31 - 1`.

## Given the Binary Tree definition

```.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}```/**
* 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;
*     }
* }
*/```Code language: Java (java)```

## 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;
}
}
```Code language: Java (java)```

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);
}
}
```Code language: Java (java)```

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);
}
}
}
```Code language: Java (java)```
Tags:
Subscribe
Notify of 