text: Lowest Common Ancestor in a Binary Search Tree . | A recursive C program to find LCA of two nodes n1 and n2 . ; Function to find LCA of n1 and n2 . The function assumes that both n1 and n2 are present in BST ; If both n1 and n2 are smaller than root , then LCA lies in left ; If both n1 and n2 are greater than root , then LCA lies in right ; Helper function that allocates a new node with the given data . ; Driver program to test lca ( ) ; Let us construct the BST shown in the above figure
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left , * right ; } ; struct node * lca ( struct node * root , int n1 , int n2 ) { while ( root != NULL ) { if ( root -> data > n1 && root -> data > n2 ) root = root -> left ; else if ( root -> data < n1 && root -> data < n2 ) root = root -> right ; else break ; } return root ; } struct node * newNode ( int data ) { struct node * node = ( struct node * ) malloc ( sizeof ( struct node ) ) ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } int main ( ) { struct node * root = newNode ( 20 ) ; root -> left = newNode ( 8 ) ; root -> right = newNode ( 22 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 12 ) ; root -> left -> right -> left = newNode ( 10 ) ; root -> left -> right -> right = newNode ( 14 ) ; int n1 = 10 , n2 = 14 ; struct node * t = lca ( root , n1 , n2 ) ; printf ( " LCA ▁ of ▁ % d ▁ and ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , n1 , n2 , t -> data ) ; n1 = 14 , n2 = 8 ; t = lca ( root , n1 , n2 ) ; printf ( " LCA ▁ of ▁ % d ▁ and ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , n1 , n2 , t -> data ) ; n1 = 10 , n2 = 22 ; t = lca ( root , n1 , n2 ) ; printf ( " LCA ▁ of ▁ % d ▁ and ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , n1 , n2 , t -> data ) ; getchar ( ) ; return 0 ; }