Binary tree visit: get from one leaf to another leaf

1
votes

Problem: I have a binary tree, all leaves are numbered (from left to right, starting from 0) and no connection exists between them.

I want an algorithm that, given two indices (of 2 distinct leaves), visits the tree starting from the greater leaf (the one with the higher index) and gets to the lower one.

The internal nodes of the tree do not contain any useful information.

I should chose the path based only on the leaves indices. The path start from a leaf and terminates on a leaf, and of course I can access a leaf if I know its index (through an array of pointers)

The tree is static, no insertion or deletion of nodes is allowed.

I have developed an algorithm to do it but it really sucks... any ideas?

2
algorithmdata-structuresbinary-tree

2 Answers

4
votes

One option would be to find the least common ancestor of the two nodes, along with the sequence of nodes you should take from each node to get to that ancestor. Here's a sketch of the algorithm:

  1. Starting from each node, walk back up to that node's parent until you reach the root. Count the number of nodes on the path from each node to the root. Let the height of the first node be h1 and the height of the second node be h2.

  2. Let h = min(h1, h2). This is the height of the higher of the two nodes.

  3. Starting from each node, keep following the node's parent pointer until both nodes are at height h. Record the nodes you followed during this step. At this point, both nodes are at the same height.

  4. Until you find a common node, keep marching upwards from each node to its parent. Eventually you will hit their common ancestor. At this point, follow the path from the first node up to this ancestor, then down the path from the ancestor down to the second node.

In the worst case, this takes O(h) time and O(h) space, where h is the height of the tree. For a balanced binary tree is this O(lg n) time and space, which is quite good.

If you're interested in a Much More Hardcore version of this algorithm, consider looking into Tarjan's Least Common Ancestors algorithm, which with linear preprocessing time, can be used to find the least common ancestor much more rapidly than this.

Hope this helps!

0
votes

Distance between any two nodes can be calculated with the help of lowest common ancestor:

 Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)

where lca is lowest common ancestor.

see this for more help about this algorithm and see this video for learning how to calculate lca.