# Shortest Path in Binary Trees Codechef Solution|Problem Code: BINTREE

Hello coders, today we are going to solve Shortest Path in Binary Trees Codechef Solution.

## Problem

Consider an infinite full binary tree (each node has two children except the leaf nodes) defined as follows. For a node labelled v its left child will be labelled 2*v and its right child will be labelled 2*v+1. The root is labelled as 1.

You are given N queries of the form i j. For each query, you have to print the length of the shortest path between node labelled i and node labelled j.

### Input

First line contains N, the number of queries. Each query consists of two space separated integers i and j in one line.

### Output

For each query, print the required answer in one line.

### Constraints

• 1 ≤ N ≤ 105
• 1 ≤ i,j ≤ 109

### Example

```Input:
3
1 2
2 3
4 3
Output:
1
2
3
```

### Explanation

For first query, 1 is directly connected to 2 by an edge. Hence distance 1.

### Shortest Path in Binary Trees CodeChef Solution in JAVA

```import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int x = sc.nextInt();
int y = sc.nextInt();
int count=0;
while(x!=y){
if(x > y){
x=x/2;
}
else{
y=y/2;
}
count++;
}
System.out.println(count);
}
}catch(Exception e){
return;
}
}
}```

### Shortest Path in Binary Trees CodeChef Solution in CPP

```#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int a,b;
int count=0;
cin>>a>>b;
while(a!=b){
if(a>b){
a /=2;
count ++;
}
else{
b /=2;
count++;
}
}
cout<<count<<endl;
}
return 0;
}
```

### Shortest Path in Binary Trees CodeChef Solution in Python

```if __name__ == "__main__":
n = int(input())
for i in range(n):
i,j = list(map(int, input().split()))
maxi = max(i,j)
mini = min(i, j)
count = 0
while(True):
if(maxi == mini):
break
else:
maxi = maxi//2
count +=1
if(maxi != max(maxi, mini)):
maxi,mini = mini,maxi
print(count)```

Disclaimer: The above Problem (Shortest Path in Binary Trees) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.

Sharing Is Caring