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:
- The number of nodes in the tree is between
1
and1000
. - node.val is
0
or1
. - 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); } } }