Distance between two nodes of binary tree with node values from 1 to N | C ++ program to find minimum distance between two nodes in binary tree ; Function to get minimum path distance ; count bit length of n1 and n2 ; find bit difference and maxBit ; calculate result by formula ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minDistance ( int n1 , int n2 ) { int bitCount1 = floor ( log2 ( n1 ) ) + 1 ; int bitCount2 = floor ( log2 ( n2 ) ) + 1 ; int bitDiff = abs ( bitCount1 - bitCount2 ) ; int maxBitCount = max ( bitCount1 , bitCount2 ) ; if ( bitCount1 > bitCount2 ) { n2 = n2 * pow ( 2 , bitDiff ) ; } else { n1 = n1 * pow ( 2 , bitDiff ) ; } int xorValue = n1 ^ n2 ; int bitCountXorValue ; if ( xorValue == 0 ) bitCountXorValue = 1 ; else { bitCountXorValue = floor ( log2 ( xorValue ) ) + 1 ; } int disSimilarBitPosition = maxBitCount - bitCountXorValue ; int result = bitCount1 + bitCount2 - 2 * disSimilarBitPosition ; return result ; } int main ( ) { int n1 = 12 , n2 = 5 ; cout << minDistance ( n1 , n2 ) ; return 0 ; }