The Path in Binary

There is a shorter way to find the path to a position. Repeated division by 2 is how we write a number in binary. The remainders, read from the last to the first, are the binary digits. Position 12 is 1100 in binary. The last division, $1/2 = 0$ remainder $1$ , gives the leading 1, and that 1 stands for the root. The digits after it, 100, are the directions we found: right, left, left.

So, to find the path from the root to position $p$ , write $p$ in binary, drop the leading 1, and read the remaining digits as directions: 0 for left and 1 for right.

Check it on the open slot in our heap of six elements, position 7. It is 111 in binary. Drop the leading 1 and read 11: right, then right. That is the path the divisions gave.

In code, Java’s Integer.toBinaryString writes a number in binary, so pathTo is short:

// The directions from the root to the node at position, one character per
// step: '0' for left and '1' for right. The root is position 1.
private String pathTo(int position) {
  String binary = Integer.toBinaryString(position);
  return binary.substring(1);  // drop the leading 1, which is the root
}

The path to the next open slot is pathTo(size + 1). remove needs the last node instead, which is position size, so its path is pathTo(size).

A number $p$ has about $lo g_{2} p$ binary digits, so the path has about $lo g n$ steps. Following it costs $O (lo g n)$ , not the $O (n)$ of searching the tree in level order for the first missing child.