Lowest Common Ancestor in a Binary Tree | Set 2 ( Using Parent Pointer ) |  ; Java program to find lowest common ancestor using parent pointer A tree 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
import java . util . HashMap ; import java . util . Map ; class Node { int key ; Node left , right , parent ; Node ( int key ) { this . key = key ; left = right = parent = null ; } } class BinaryTree { Node root , n1 , n2 , lca ; Node insert ( Node node , int key ) { if ( node == null ) return new Node ( 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 != null ) { ++ 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 -- != 0 ) n1 = n1 . parent ; while ( n1 != null && n2 != null ) { if ( n1 == n2 ) return n1 ; n1 = n1 . parent ; n2 = n2 . parent ; } return null ; } public static void main ( String [ ] args ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = tree . insert ( tree . root , 20 ) ; tree . root = tree . insert ( tree . root , 8 ) ; tree . root = tree . insert ( tree . root , 22 ) ; tree . root = tree . insert ( tree . root , 4 ) ; tree . root = tree . insert ( tree . root , 12 ) ; tree . root = tree . insert ( tree . root , 10 ) ; tree . root = tree . insert ( tree . root , 14 ) ; tree . n1 = tree . root . left . right . left ; tree . n2 = tree . root . right ; tree . lca = tree . LCA ( tree . n1 , tree . n2 ) ; System . out . println ( " LCA ▁ of ▁ " + tree . n1 . key + " ▁ and ▁ " + tree . n2 . key + " ▁ is ▁ " + tree . lca . key ) ; } }