Number of turns to reach from one node to other in binary tree | C ++ Program to count number of turns in a Binary Tree . ; A Binary Tree Node ; Utility function to create a new tree Node ; Utility function to find the LCA of two given values n1 and n2 . ; Base case ; If either n1 or n2 matches with root 's key, report the presence by  returning root (Note that if a key  is ancestor of other, then the  ancestor key becomes LCA ; Look for keys in left and right subtrees ; If both of the above calls return Non - NULL , then one key is present in once subtree and other is present in other , So this node is the LCA ; Otherwise check if left subtree or right subtree is LCA ; function count number of turn need to reach given node from it 's LCA we have two way to ; if found the key value in tree ; Case 1 : ; Case 2 : ; Function to find nodes common to given two nodes ; there is no path between these two node ; case 1 : ; count number of turns needs to reached the second node from LCA ; count number of turns needs to reached the first node from LCA ; case 2 : ; count number of turns needs to reached the second node from LCA ; count number of turns needs to reached the first node from LCA1 ; Driver program to test above functions ; Let us create binary tree given in the above example
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { struct Node * left , * right ; int key ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return temp ; } struct Node * findLCA ( struct Node * root , int n1 , int n2 ) { if ( root == NULL ) return NULL ; if ( root -> key == n1 root -> key == n2 ) return root ; Node * left_lca = findLCA ( root -> left , n1 , n2 ) ; Node * right_lca = findLCA ( root -> right , n1 , n2 ) ; if ( left_lca && right_lca ) return root ; return ( left_lca != NULL ) ? left_lca : right_lca ; } bool CountTurn ( Node * root , int key , bool turn , int * count ) { if ( root == NULL ) return false ; if ( root -> key == key ) return true ; if ( turn == true ) { if ( CountTurn ( root -> left , key , turn , count ) ) return true ; if ( CountTurn ( root -> right , key , ! turn , count ) ) { * count += 1 ; return true ; } } else { if ( CountTurn ( root -> right , key , turn , count ) ) return true ; if ( CountTurn ( root -> left , key , ! turn , count ) ) { * count += 1 ; return true ; } } return false ; } int NumberOFTurn ( struct Node * root , int first , int second ) { struct Node * LCA = findLCA ( root , first , second ) ; if ( LCA == NULL ) return -1 ; int Count = 0 ; if ( LCA -> key != first && LCA -> key != second ) { if ( CountTurn ( LCA -> right , second , false , & Count ) || CountTurn ( LCA -> left , second , true , & Count ) ) ; if ( CountTurn ( LCA -> left , first , true , & Count ) || CountTurn ( LCA -> right , first , false , & Count ) ) ; return Count + 1 ; } if ( LCA -> key == first ) { CountTurn ( LCA -> right , second , false , & Count ) ; CountTurn ( LCA -> left , second , true , & Count ) ; return Count ; } else { CountTurn ( LCA -> right , first , false , & Count ) ; CountTurn ( LCA -> left , first , true , & Count ) ; return Count ; } } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 7 ) ; root -> left -> left -> left = newNode ( 8 ) ; root -> right -> left -> left = newNode ( 9 ) ; root -> right -> left -> right = newNode ( 10 ) ; int turn = 0 ; if ( ( turn = NumberOFTurn ( root , 5 , 10 ) ) ) cout << turn << endl ; else cout << " Not ▁ Possible " << endl ; return 0 ; }