EPI 9.5  Sum RootToLeaf Paths of Binary Tree (Binary Data)
Reference: EPI 9.5
Problem
Consider a binary tree in which each node contains a
binary digit
. A roottoleaf 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 roottoleaf paths.
Example:
1  Input: [1,0,1,1,1] 
Analysis
Methods:
 BruteForce
 Compute the
leaves
and store in a list.  Store the
childparent 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 leaftoroot paths (#leaves).
 $O(N)$: Traverse the whole tree to store leaves and childparent mapping.
 $O(Lh)$: Compute the sum.
 Space: $O(N)$
 Compute the
 OnePass
 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
BruteForce
Note:
 Learn using
preorder
orinorder
traversal to set up childparent mapping.  This code fails! See details below.
1  private static HashMap<BinaryTreeNode<Integer>, BinaryTreeNode<Integer>> map; 
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:
1  Input: [1,0,1,1,1] 
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:
1  BinaryTreeNode<Integer> b1 = new BinaryTreeNode<>(1); 
The hash code values of some nodes are the same! Then I checked out the hashCode
method in the BinaryTreeNode
class:
1 

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.
1  System.out.println(b1.hashCode()); // 1802598046 
Finally, I reran the test and it passed…
The takeaway of this 1hour 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
.
OnePass
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 theresult
.
1  public static int sumRootToLeaf(BinaryTreeNode<Integer> tree) { 