Reference: EPI 9.5

## Problem

Consider a binary tree in which each node contains a binary digit. A root-to-leaf path can be associated with a binary number (the MSB is at the root). Design an algorithm to compute the sum of the binary numbers represented by the root-to-leaf paths.

Example:

## Analysis

Methods:

1. Brute-Force
• Compute the leaves and store in a list.
• Store the child-parent mapping in a hash table.
• For each leaf in the list, we traverse from the leaf to the root, and sum up digits to get a value of each path.
• Sum those values to obtain the result.
• Time: $O(N + Lh)$ where $L$ is the number of leaf-to-root paths (#leaves).
• $O(N)$: Traverse the whole tree to store leaves and child-parent mapping.
• $O(Lh)$: Compute the sum.
• Space: $O(N)$
2. One-Pass
• Paths share nodes and it is not necessary to repeat computations for shared nodes.
• Pass down the result as an argument to the leaf node and then return the result.
• In a decimal perspective, we double the result, equivalent to left shirting by one.
• Time: $O(N)$
• Space: $O(h)$

## Code

### Brute-Force

Note:

• Learn using preorder or inorder traversal to set up child-parent mapping.
• This code fails! See details below.

Why it fails?

Since it failed the first test case, I tried to come up with some simple test cases and located the bug. It was strange that it could pass some cases but could not pass the other. For example, it could not pass the following test case:

After a whole examination on the code, I believed the bug should be in the method findParentsAndLeaves. As for this case, map.put(tree, parent) did not correctly set the mapping from b4 to b2. However, if I changed the data values of all nodes from [1,0,1,1,1] to [1,2,3,4,5], it worked as expected.

So I started doubting that the problem might be related to the hashCode method in the class BinaryTreeNode. The testing code for the hash code is as follows:

The hash code values of some nodes are the same! Then I checked out the hashCode method in the BinaryTreeNode class:

This is reason why the hash code values were equal. Without hesitation, I uncommented it and let it calculate the hash code by the address of an object.

Finally, I reran the test and it passed…

The takeaway of this 1-hour debugging journey is that if nodes in a binary tree are not unique, be careful of using mapping. Since it is not a BstNode, I think the test’s writer should not override the hashCode method in BinaryTreeNode.

### One-Pass

Note:

• Be careful of the corner cases, they are very annoying.
• It should return the result immediately when it hits a leaf node.
• Otherwise, it will return x + y = 0 instead of the result.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.