## 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: 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 `` or `1`.
3. 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);
}
}
}
``````