TREECON - Editorial

PROBLEM LINK:

Practice

Contest

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.

//