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:
