Lowest Common Ancestor in a Binary Tree | Set 1 | C ++ program to find LCA of n1 and n2 using one traversal of Binary Tree . It handles all cases even when n1 or n2 is not there in Binary Tree ; A Binary Tree Node ; Utility function to create a new tree Node ; This function returns pointer to LCA of two given values n1 and n2 . v1 is set as true by this function if n1 is found v2 is set as true by this function if n2 is found ; Base case ; If either n1 or n2 matches with root 's key, report the presence  by setting v1 or v2 as true and return 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 ; Returns true if key k is present in tree rooted with root ; This function returns LCA of n1 and n2 only if both n1 and n2 are present in tree , otherwise returns NULL ; ; Initialize n1 and n2 as not visited ; Find lca of n1 and n2 using the technique discussed above ; Return LCA only if both n1 and n2 are present in tree ; Else return NULL ; Driver program to test above functions
#include <iostream> 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 * findLCAUtil ( struct Node * root , int n1 , int n2 , bool & v1 , bool & v2 ) { if ( root == NULL ) return NULL ; if ( root -> key == n1 ) { v1 = true ; return root ; } if ( root -> key == n2 ) { v2 = true ; return root ; } Node * left_lca = findLCAUtil ( root -> left , n1 , n2 , v1 , v2 ) ; Node * right_lca = findLCAUtil ( root -> right , n1 , n2 , v1 , v2 ) ; if ( left_lca && right_lca ) return root ; return ( left_lca != NULL ) ? left_lca : right_lca ; } bool find ( Node * root , int k ) { if ( root == NULL ) return false ; if ( root -> key == k || find ( root -> left , k ) || find ( root -> right , k ) ) return true ; return false ; } Node * findLCA ( Node * root , int n1 , int n2 ) { bool v1 = false , v2 = false ; Node * lca = findLCAUtil ( root , n1 , n2 , v1 , v2 ) ; if ( v1 && v2 || v1 && find ( lca , n2 ) || v2 && find ( lca , n1 ) ) return lca ; return NULL ; } 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 ) ; Node * lca = findLCA ( root , 4 , 5 ) ; if ( lca != NULL ) cout << " LCA ( 4 , ▁ 5 ) ▁ = ▁ " << lca -> key ; else cout << " Keys ▁ are ▁ not ▁ present ▁ " ; lca = findLCA ( root , 4 , 10 ) ; if ( lca != NULL ) cout << " nLCA ( 4 , ▁ 10 ) ▁ = ▁ " << lca -> key ; else cout << " nKeys ▁ are ▁ not ▁ present ▁ " ; return 0 ; }