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: 

1
2
3
4
5
6
7
Input: [1,0,1,1,1]
    1
   / \
  0   1
 / \
1   1
Output: 13 = (101) + (101) + (11)

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private static HashMap<BinaryTreeNode<Integer>, BinaryTreeNode<Integer>> map;
private static ArrayList<BinaryTreeNode<Integer>> leaves;

public static int sumRootToLeaf(BinaryTreeNode<Integer> tree) {
  map = new HashMap<>();
  leaves = new ArrayList<>();
  findParentsAndLeaves(tree, null); // root's parent is null

  int sum = 0; // sum up
  for (BinaryTreeNode<Integer> leaf : leaves) {
    int val = 0;
    BinaryTreeNode<Integer> p = leaf;
    int k; // bit offset
    for (k = 0, p = leaf; p != null; ++k, p = map.get(p)) {
      val = val + (p.data << k);
    }
    sum += val;
  }
  return sum;
}

// Preorder traversal
private static void findParentsAndLeaves(BinaryTreeNode<Integer> tree,  BinaryTreeNode<Integer> parent) {
  if (tree == null) return;
  // store leaves
  if (tree.left == null && tree.right == null) leaves.add(tree);
  // map child-parent
  map.put(tree, parent);

  findParentsAndLeaves(tree.left, tree);
  findParentsAndLeaves(tree.right, tree);
}

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
2
3
4
5
6
7
Input: [1,0,1,1,1]
    1              b1
   / \            / \
  0   1    <=>   b2  b3
 / \            / \
1   1          b4  b5
Output: 13 = (101) + (101) + (11)

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
2
3
4
5
6
7
8
9
10
11
12
BinaryTreeNode<Integer> b1 = new BinaryTreeNode<>(1);
BinaryTreeNode<Integer> b2 = new BinaryTreeNode<>(0);
BinaryTreeNode<Integer> b3 = new BinaryTreeNode<>(1);
BinaryTreeNode<Integer> b4 = new BinaryTreeNode<>(1);
BinaryTreeNode<Integer> b5 = new BinaryTreeNode<>(1);
b1.left = b2; b1.right = b3;
b2.left = b4; b2.right = b5;
System.out.println(b1.hashCode()); // 31491009
System.out.println(b2.hashCode()); // 1013855
System.out.println(b3.hashCode()); // 30752
System.out.println(b4.hashCode()); // 30752   <======= The problem is here
System.out.println(b5.hashCode()); // 30752

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

1
2
3
4
@Override
public int hashCode() {
  return Objects.hash(data, left, right);
}

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
2
3
4
5
System.out.println(b1.hashCode()); // 1802598046
System.out.println(b2.hashCode()); // 659748578
System.out.println(b3.hashCode()); // 240650537    => Work well!
System.out.println(b4.hashCode()); // 483422889
System.out.println(b5.hashCode()); // 2088051243

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int sumRootToLeaf(BinaryTreeNode<Integer> tree) {
  if (tree == null) return 0;
  return sum(tree, 0);
}

private static int sum(BinaryTreeNode<Integer> node, int result) {
  if (node == null) return 0;

  result = (result << 1) + node.data;

  if (node.left == null && node.right == null) {
    return result;
  }

  int x = sum(node.left, result);
  int y = sum(node.right, result);

  return x + y;
}