Given a Binary Tree Print the Shortest Path

Implementation

// Writing a program in C++ to find the shortest between the nodes i and j. 
#include <bits/stdc++.h>
using namespace std;


// the given function will print the path between nodes i and j.
void Short__Path(int i, int j, int k, int m, int n)
{
	// The path1 of the function generally stores the path of the node i to lca, and path2 generally stores the path of the node j to lca.  
	vector<int> path1, path2;
	int x = m - 1;


	// we have to push node i into path1.
	path1.push_back(i);


	// Then we must keep pushing the parent node mentioned as i to path1 until we reach the lca. 
	while (x != k) {
		path1.push_back(i / 2);
		i = i / 2;
		x--;
	}
	int y = n - 1;


	// we have to push node j into path2.
	path2.push_back(j);


	// Then we must keep pushing the parent node mentioned as j to path2 until we reach the lca. 
	while (y != k)
	{
		path2.push_back(j / 2);
		j = j / 2;
		y--;
	}


	// Now, we will print the path of node i to lca. 
	for (int l = 0; l < path1.size(); l++)
		cout << path1[l] << " ";


	// Now, we will print the path from lca to node j.
	for (int l = path2.size() - 2; l >= 0; l--)
		cout << path2[l] << " ";
	cout << endl;
}


// After this, we will return the shortest or closest distance between the nodes mentioned as i and j. 
int Shortest__Dist(int i, int j)
{
	// We are creating a vector that will help us store the binary form of the nodes, i.e., i and j. 
	vector<int> v1, v2;


	// searching the binary form of the i and j.
	int p1 = i;
	int p2 = j;
	while (i != 0)
	{
		v1.push_back(i % 2);
		i = i / 2;
	}
	while (j != 0) {
		v2.push_back(j % 2);
		j = j / 2;
	}


	// We know that the binary form will be in reverse order, so we have to reverse the vectors. 
	reverse(v1.begin(), v1.end());
	reverse(v2.begin(), v2.end());


	// Now, we are supposed to find the k value, the lca (i,j ). 
	int m = v1.size(), n = v2.size(), k = 0;
	if (m < n)
	{
		while (k < m && v1[k] == v2[k])
			k++;
	}
	else {
		while (k < n && v1[k] == v2[k])
			k++;
	}


	Short__Path(p1, p2, k - 1, m, n);
	return m + n - 2 * k;
}


// writing the main code
int main()
{
	cout << Shortest__Dist(1, 2) << endl;
	cout << Shortest__Dist(4, 3) << endl;
	return 0;
}

Output:

Example 2

// Writing a program in C# language to find out the shortest between the nodes i and j. 
using System;
using System.Collections.Generic;
	
class TFT
{
// the given function will print the path between nodes i and j.
static void Short__Path(int i, int j, int k, int m,
									int n)
{
	// The path1 of the function generally stores the path of the node i to lca, and path2 generally stores the path of the node j to lca.  
	List<int> path1=new List<int>(),
					path2=new List<int>();
	int x = m - 1;
// we have to push node i into path1. 
	path1.Add(i);
// Then we must keep pushing the parent node mentioned as i to path1 until we reach the lca. 
	while (x != k)
	{
		path1.Add(i / 2);
		i = i / 2;
		x--;
	}
	int y = n - 1;
// we have to push node j into path2.
	path2.Add(j);
// Then we must keep pushing the parent node mentioned as j to path2 until we reach the lca. 
	while (y != k)
	{
		path2.Add(j / 2);
		j = j / 2;
		y--;
	}
// Now, we will print the path of node i to lca. 
	for (int l = 0; l < path1.Count; l++)
		Console.Write( path1[l] + " ");
// Now, we will print the path from lca to node j.
	for (int l = path2.Count - 2; l >= 0; l--)
		Console.Write( path2[l] + " ");
	Console.WriteLine();
}
// After this, we will return the shortest or closest distance between the nodes mentioned as i and j. 
static int Shortest__Dist(int i, int j)
{
// We are creating a vector that will help us store the binary form of the nodes, i.e., i and j. 
	List<int> v1=new List<int>(),
					v2=new List<int>();
// searching the binary form of the i and j.
	int p1 = i;
	int p2 = j;
	while (i != 0)
	{
		v1.Add(i % 2);
		i = i / 2;
	}
	while (j != 0)
	{
		v2.Add(j % 2);
		j = j / 2;
	}
// We know that the binary form will be in reverse order, so we have to reverse the vectors. 
	v1.Reverse();
	v2.Reverse();
// Now, we are supposed to find the k value, the lca (i,j ).
	int m =v1.Count, n =v2.Count, k = 0;
	if (m < n)
	{
		while (k < m && v1[k] == v2[k])
			k++;
	}
	else
	{
		while (k < n && v1[k] == v2[k])
			k++;
	}


	Short__Path(p1, p2, k - 1, m, n);
	return m + n - 2 * k;
}
// writing the main code
public static void Main(String []args)
{
	Console.WriteLine( Shortest__Dist(1, 2) );
	Console.WriteLine(Shortest__Dist(4, 3) );
}
}

Output:

Example 3

// Writing a program in Java to find the shortest between the nodes i and j. 
import java.util.*;


class TFT
{
// the given function will print the path between nodes i and j.
static void Short__Path(int i, int j, int k, int m,
									int n)
{
	// The path1 of the function generally stores the path of the node i to lca, and path2 generally stores the path of the node j to lca.  
	Vector<Integer> path1=new Vector<Integer>(),
					path2=new Vector<Integer>();
	int x = m - 1;
// we have to push node i into path1.
	path1.add(i);


	// Then we must keep pushing the parent node mentioned as i to path1 until we reach the lca. 
	while (x != k)
	{
		path1.add(i / 2);
		i = i / 2;
		x--;
	}
	int y = n - 1;
// we have to push node j into path2.
	path2.add(j);
// Then we must keep pushing the parent node mentioned as j to path2 until we reach the lca. 
	while (y != k)
	{
		path2.add(j / 2);
		j = j / 2;
		y--;
	}


	// Now, we will print the path of node i to lca. 
	for (int l = 0; l < path1.size(); l++)
		System.out.print( path1.get(l) + " ");
// Now, we will print the path from lca to node j.
	for (int l = path2.size() - 2; l >= 0; l--)
		System.out.print( path2.get(l) + " ");
	System.out.println();
}
// After this, we will return the shortest or closest distance between the nodes mentioned as i and j. 
static int Shortest__Dist(int i, int j)
{
// We are creating a vector that will help us store the nodes' binary form, i.e., i and j. 
	Vector<Integer> v1=new Vector<Integer>(),
					v2=new Vector<Integer>();
// searching the binary form of the i and j.
	int p1 = i;
	int p2 = j;
	while (i != 0)
	{
		v1.add(i % 2);
		i = i / 2;
	}
	while (j != 0)
	{
		v2.add(j % 2);
		j = j / 2;
	}
// We know that the binary form will be in reverse order, so we have to reverse the vectors. 
	Collections.reverse(v1);
	Collections.reverse(v2);
// Now, we are supposed to find the k value, the lca (i,j ).
	int m = v1.size(), n = v2.size(), k = 0;
	if (m < n)
	{
		while (k < m && v1.get(k) == v2.get(k))
			k++;
	}
	else
	{
		while (k < n && v1.get(k) == v2.get(k))
			k++;
	}


	Short__Path(p1, p2, k - 1, m, n);
	return m + n - 2 * k;
}
// writing the main code
public static void main(String args[])
{
	System.out.println( Shortest__Dist(1, 2) );
	System.out.println(Shortest__Dist(4, 3) );
}
}

Output:

Example 4

<script>
// Writing a program in Javascript language to find out the shortest between the nodes i and j. 
function Short__Path(i,j,k,m,n)
{
	// the given function will print the path between nodes i and j.
// The path1 of the function generally stores the path of the node i to lca, and path2 generally stores the path of the node j to lca.  
	let path1=[];
	let path2=[];
	let x = m - 1;
// we have to push node i into path1.
	path1.push(i);
// Then we must keep pushing the parent node mentioned as i to path1 until we reach the lca. 
	while (x != k)
	{
		path1.push(Math.floor(i / 2));
		i = Math.floor(i / 2);
		x--;
	}
	let y = n - 1;
// we have to push node j into path2.
	path2.push(j);
// Then we must keep pushing the parent node mentioned as j to path2 until we reach the lca. 
	while (y != k)
	{
		path2.push(Math.floor(j / 2));
		j = Math.floor(j / 2);
		y--;
	}
// Now, we will print the path of node i to lca. 
	for (let l = 0; l < path1.length; l++)
		document.write( path1[l] + " ");
// Now, we will print the path from lca to node j.
	for (let l = path2.length - 2; l >= 0; l--)
		document.write( path2[l] + " ");
	document.write("<br>");
}
// After this, we will return the shortest or closest distance between the nodes mentioned as i and j. 
function Shortest__Dist(i,j)
{
	// We are creating a vector that will help us store the nodes' binary form, i.e., i and j. 
	let v1=[];
	let v2=[];
// searching the binary form of the i and j.
	let p1 = i;
	let p2 = j;
	while (i != 0)
	{
		v1.push(i % 2);
		i = Math.floor(i / 2);
	}
	while (j != 0)
	{
		v2.push(j % 2);
		j = Math.floor(j / 2);
	}
// We know that the binary form will be in reverse order, so we have to reverse the vectors. 
	v1.reverse();
	v2.reverse();
// Now, we are supposed to find the k value, the lca (i,j ).
	let m =v1.length, n =v2.length, k = 0;
	if (m < n)
	{
		while (k < m && v1[k] == v2[k])
			k++;
	}
	else
	{
		while (k < n && v1[k] == v2[k])
			k++;
	}


	Short__Path(p1, p2, k - 1, m, n);
	return m + n - 2 * k;
}
// writing the main code
document.write( Shortest__Dist(1, 2) +"<br>");
document.write(Shortest__Dist(4, 3) +"<br>");
</script>

Output: