PROBLEM LINK:
Author: Amrit Raj
Tester: Chinmay Rakshit
Editorialist: Chinmay Rakshit
DIFFICULTY:
MEDIUM
PREREQUISITES:
MATH
PROBLEM:
given a balanced binary tree where nodes are labeled as 2v and 2v+1 you have to find the distance between the two query node having the lowest common ancestor.
and print the distance + 1 as the last line suggests the line joins the two nodes.
QUICK EXPLANATION:
To solve this first we find the height of each node respectively for that I used
h1=log2l(x)
h2=log2l(y)
Now which of them is the bigger one we have to bring the higher value to equal to h1 and divide the higher value by 2
As soon as they are at the same level then we have to find the lowest common ancestor and we do here count+=2
So the final answer is count + 1 as I have already mentioned there is also a connection between the nodes so the last increment was for that.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.