Lowest Common Ancestor in a Binary Tree | Set 2 ( Using Parent Pointer ) | C ++ program to find lowest common ancestor using parent pointer ; A Tree Node ; A utility function to create a new BST node ; A utility function to insert a new node with given key in Binary Search Tree ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; A utility function to find depth of a node ( distance of it from root ) ; To find LCA of nodes n1 and n2 in Binary Tree ; Find depths of two nodes and differences ; If n2 is deeper , swap n1 and n2 ; Move n1 up until it reaches the same level as n2 ; Now n1 and n2 are at same levels ; Driver method to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { Node * left , * right , * parent ; int key ; } ; Node * newNode ( int item ) { Node * temp = new Node ; temp -> key = item ; temp -> parent = temp -> left = temp -> right = NULL ; return temp ; } Node * insert ( Node * node , int key ) { if ( node == NULL ) return newNode ( key ) ; if ( key < node -> key ) { node -> left = insert ( node -> left , key ) ; node -> left -> parent = node ; } else if ( key > node -> key ) { node -> right = insert ( node -> right , key ) ; node -> right -> parent = node ; } return node ; } int depth ( Node * node ) { int d = -1 ; while ( node ) { ++ d ; node = node -> parent ; } return d ; } Node * LCA ( Node * n1 , Node * n2 ) { int d1 = depth ( n1 ) , d2 = depth ( n2 ) ; int diff = d1 - d2 ; if ( diff < 0 ) { Node * temp = n1 ; n1 = n2 ; n2 = temp ; diff = - diff ; } while ( diff -- ) n1 = n1 -> parent ; while ( n1 && n2 ) { if ( n1 == n2 ) return n1 ; n1 = n1 -> parent ; n2 = n2 -> parent ; } return NULL ; } int main ( void ) { Node * root = NULL ; root = insert ( root , 20 ) ; root = insert ( root , 8 ) ; root = insert ( root , 22 ) ; root = insert ( root , 4 ) ; root = insert ( root , 12 ) ; root = insert ( root , 10 ) ; root = insert ( root , 14 ) ; Node * n1 = root -> left -> right -> left ; Node * n2 = root -> right ; Node * lca = LCA ( n1 , n2 ) ; printf ( " LCA ▁ of ▁ % d ▁ and ▁ % d ▁ is ▁ % d ▁ STRNEWLINE " , n1 -> key , n2 -> key , lca -> key ) ; return 0 ; }