# Short Java 8 and dfs solution

• The idea is to first represent the tree as a map, that contains the tree in the form of
Node position number --> Node value , where the Node number is the position of the node in a complete tree.

Then, we just do a dfs on the above tree to accumulate all the root to leaf path sums.

``````Lets take a tree example
10
/  \
20     30
/ \     / \
40  50  60   70
``````

For the above tree,
the node positions are as follows,
root's position = 1,
left child position = parent_position * 2
right child position = parent_position * 2 + 1
Based on the above complete tree positions, the map generated for the above example would be
1 --> 10
2 --> 20
3 --> 30
4 --> 40
5 --> 50
6 --> 60
7 --> 70

To generate these positions from the given input,
if the input number is 314
we extract the digits to level = 3, positionInLevel = 1, value = 4
and the formula I arrived at to get the node's position in complete tree = [2 ^ (level-1)] + positionInLevel - 1

Now that we have the above map generated,
we do a simple dfs starting from the root, and keep accumulating the sum, once we reach a leaf, we add the accumulated sum to the result.

``````    public int pathSum(int[] nums) {
Map<Integer, Integer> positionToNodeMap = new HashMap<>();
Arrays.stream(nums).forEach( num -> {
int[] digits = IntStream.range(0, 3).map(i -> (num + "").charAt(i) - '0').toArray();
positionToNodeMap.put((int)Math.pow(2, digits[0] - 1) - 1 + digits[1], digits[2]);
});
int[] res = new int[1];
dfs(1, 0, res, positionToNodeMap);
return res[0];
}

private void dfs(int cur, int sum, int[] res, Map<Integer, Integer> map) {
if(!map.containsKey(cur)) return;
int left = cur * 2, right = cur * 2 + 1, totalSum = sum + map.get(cur);
if(!map.containsKey(left) && !map.containsKey(right)) { res[0] += totalSum; return; } // Leaf node
dfs(left, totalSum, res, map);
dfs(right, totalSum, res, map);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.