where root = 1, Left nodes (L) = 2n and Right nodes (R) = 2n+1. In getting the Common Ancestor, we need to compare the ancestor of Left nodes and Right Nodes until the result is the same or reaches to 1 as their common ancestor.
(1)
/ \
/ \
(2) (3)
/ \ / \
/ \ / \
(4) (5) (6) (7)For example, The ancestor of : > 2 and 3 is 1. > 5 and 6 is 1. > 4 and 5 is 2. > 6 and 7 is 3. > and so on.
While(true): if(L > R) Then: L = L << 1; else if(R > L) Then: R = R << 1; else: break;
print(R)
there're faster algorithms.
Faster than log(max(L, R))? Can you tell the answer without looking at binary representation?
I don't know if I got him right, but by saying that left child of n is 2n and right child of n is 2n+1, I assume he's talking about a full binary tree. In that case, the concept of LCA makes little sense, it will always be simply the longest common prefix in the binary representation of the two nodes, which is what his function would return.
Now way :))