algorithm - Shortest path between two nodes in an infinite, complete binary tree?

Question

Suppose we have an infinite, complete binary tree where the nodes are numbered 1, 2, 3, ... by their position in a layer-by-layer traversal of the tree. Given the indices of two nodes u and v in the tree, how can we efficiently find the shortest path between them?

Thanks!

Answer 1

@Jonathan Landrum pointed out the solution in his comment. This answer fleshes out that solution.

In any tree, there is exactly one path between any two nodes. Therefore, this problem boils down to determining the unique path between those two nodes.

In any rooted tree, the shortest path between two nodes u and v can be found by finding the lowest common ancestor x of the two nodes, then concatenating the paths from u to x and from x to v. In your case, you therefore need to find the LCA of the two nodes, then glue these paths together.

Since you have an infinite binary tree, I assume that the representation is as follows:

             1
       /             
      2               3
    /              /   
   4     5         6     7
  /    /        /    / 
 8  9  10 11     12 13 14 15

This tree shape has a really interesting property if you write all the numbers in binary:

                  1
            /         
        10                  11
    /                  /         
  100        101       110       111
 /         /        /        /   
1000 1001 1010 1011 1100 1101 1110 1111

There's a few things you can notice. First, the depth of each node is given by one minus the index of the MSB.

Next, notice that if a number has binary representation b₁ b₂ ... b_n-1b_n, then its parent is b₁ b₂ ... b_n-1, and it's a left child if b_n = 0 and a right child if b_n = 1. By applying this property repeatedly, we get the following: a node u is the kth ancestor of v if and only if (v >> k) = u.

This gives us a lot to work with. Typically, you'd compute LCA(u, v) in the following way:

1. If u is deeper than v, step upward from u until you reach a node at the same depth as v (and, vice-versa, step up from v if v is deeper).
2. Walk upward from u and v at the same rate until they reach the same node. That node is the LCA.

We could implement this directly in time O(log max{u, v}) as follows. To do step (1), compute the index of the MSB of u and v to determine the depths d(u) and d(v) of each node. Let's assume WLOG that d(v) ≥ d(u). In that case, we can find the ancestor of u that's at the same depth of v in time O(1) by computing v >> (d(u) - d(v)). Nifty! To do step (2), we compare u and v and, if they're unequal, shift each one left by one spot, simulating stepping up one level. The maximum number of times we can do this is given by O(log max{u, v}), so the overall runtime is O(log max{u, v}).

However, we can speed this up exponentially by using a modified binary search. The depth of the LCA of u and v must be between 0 and min{d(u), d(v)}. Once we find a common ancestor x of u and v, we know that all ancestors of x are also common ancestors of u and v. Therefore, we can binary search over the possible depths of the LCA for u and v, computing the ancestor of each node from that depth by using a bitshift. This will run in time O(log log max{u, v}), since the maximum depth of u is O(log u) and the maximum depth of v is O(log v).

Once we've found that ancestor, we can compute the path between u and v as follows. Compute the path from u to that ancestor by repeatedly shifting away one bit from u until we arrive at the common ancestor. Compute the path from v to the ancestor in the same way, then tack on the reversal of that path to the path found in the first step. The length of this path is given by O(|log u - log v|), so the runtime is O(|log u - log v|).

On the other hand, if you just need the length of the path, you can sum the distance from u to LCA(u, v) and from LCA(u, v) to v. We can compute these values in O(log log max{u, v}) time each, so the runtime is O(log log max{u, v}).

Hope this helps!