Given a full binary tree (all nodes except leaf nodes have left and right child) represented as shown below.
If the root is labelled i, it’s left child is labelled 2*i and right child is labelled as 2*i+1.
1
/ \
2 3
/ \ / \
4 5 6 7
Given two nodes from this tree, how do we find the length of the path between them?
For example the path length between 2 and 3 is 2 (2->1->3)
Similarly path length between 4 and 1 is 2, and between 4 and 7 it is 4 (4->2->1->3->7)
In a binary tree, two nodes can be connected in two possible ways.
- Either one of the nodes can be ancestor of the other, or
- Both of them are connected by some common ancestor.
For example, take 1 and 5, 1 is an ancestor of 5.
Take 4 and 5, they are connected by their lowest common ancestor 2, so the path goes has to via 2.
So this problem can be solved by finding the Lowest Common Ancestor (LCA) of the two nodes and adding the distances between the nodes to their LCA.
We use the bottom up approach here. Start from the given two nodes and try to search for lowest common ancestor by going up since we can easily go the parent node by dividing the node by 2. While finding the LCA, we can also calculate the path length.
Since we traverse through the tree for at most the height of the tree, the time complexity will be O(log n).
Here is the C++ code.
Problem source: Codechef