Consider you have an infinitely long binary tree having the pattern as below
               1
            /     \
           2      3  
         /  \     /   \
        4  5    6  7
    .  .  .  .   .  .  .  . 
Given two nodes with values x and y, the task is to find the length of the shortest path between the two nodes.
Example 1:
Input:
X = 1
Y = 3
Output:
1
Explanation:
3 is the child of 1 so, 
distance between them is 1.
Example 2:
Input:
X = 2
Y = 2
Output:
0
Explanation:
There is no node between 2 and 2.
Your Task: 
You don't need to read input or print anything. Your task is to complete the function distance() which take integers X and Y as input parameters and returns the distance between X and Y in the infinitely long tree.
 
Expected Time Complexity: O(log (y - x))
Expected Auxiliary Space: O(1)
Constraints:
1<=X,Y<=10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: 
class Solution:
    def distance(self,X, Y):
        # code here

Solutions:
class Solution:

	def distance(self, X, Y):
		if X == Y:
			return 0
		d = 0
		while X != Y:
			if X > Y:
				X = X // 2
			else:
				Y = Y // 2
			d += 1
		return d


import math

class Solution:

	def distance(self, X, Y):
		i = 0
		Xl = int(math.log(X, 2))
		Yl = int(math.log(Y, 2))
		while Yl > Xl:
			Y = Y // 2
			i += 1
			Yl -= 1
		while Xl > Yl:
			X = X // 2
			i += 1
			Xl -= 1
		while Y != X:
			Y = Y // 2
			X = X // 2
			i += 2
		return i


class Solution:

	def parent(self, val):
		return val // 2

	def distance(self, X, Y):
		rootPathX = [X]
		rootPathY = [Y]
		while X != 1:
			X = self.parent(X)
			rootPathX.append(X)
		while Y != 1:
			Y = self.parent(Y)
			rootPathY.append(Y)
		ctr1 = 0
		ctr2 = 0
		for i in range(len(rootPathY) + len(rootPathX)):
			if rootPathX[ctr1] < rootPathY[ctr2]:
				ctr2 += 1
			elif rootPathX[ctr1] > rootPathY[ctr2]:
				ctr1 += 1
			else:
				break
		return ctr1 + ctr2


class Solution:

	def distance(self, X, Y):
		count = 0
		while X != Y:
			if X > Y:
				X = X // 2
			elif Y > X:
				Y = Y // 2
			else:
				break
			count += 1
		return count


class Solution:

	def distance(self, x, y):
		res = 0
		while x != y:
			if x > y:
				x //= 2
			else:
				y //= 2
			res += 1
		return res


class Solution:

	def distance(self, X, Y):
		ans = 0
		while X != Y and X and Y:
			if X > Y:
				X >>= 1
			else:
				Y >>= 1
			ans += 1
		return ans


import math

class Solution:

	def distance(self, X, Y):
		ans = 0
		if Y < X:
			(X, Y) = (Y, X)
		while X != Y:
			Y = int(Y / 2)
			ans += 1
			if Y < X:
				(X, Y) = (Y, X)
		return ans


class Solution:

	def distance(self, X, Y):
		count = 0
		while X != Y:
			if X > Y:
				X = X // 2
				count += 1
			if Y > X:
				Y = Y // 2
				count += 1
		return count


class Solution:

	def distance(self, X, Y):
		countx = 0
		county = 0
		while X != Y:
			if X > Y:
				X = X // 2
				countx += 1
			else:
				Y = Y // 2
				county += 1
		return countx + county


class Solution:

	def distance(self, x, y):
		d = dict()
		k = 0
		while x != 0:
			d[x] = k
			k += 1
			x //= 2
		res = 0
		while y != 0:
			if y in d:
				return d[y] + res
			res += 1
			y //= 2


class Solution:

	def distance(self, X, Y):
		if X < Y:
			(X, Y) = (Y, X)
		c = 0
		while X != Y:
			c += 1
			if X > Y:
				X = X >> 1
			if Y > X:
				Y = Y >> 1
				c += 1
		return c


class Solution:

	def distance(self, x, y):
		if x < y:
			(x, y) = (y, x)
		c = 0
		while x != y:
			c += 1
			if x > y:
				x = x >> 1
			if y > x:
				y = y >> 1
				c += 1
		return c