Lowest Common Ancestor in a Binary Tree | Set 1 | Class containing left and right child of current node and key value ; Root of the Binary Tree ; This function returns pointer to LCA of two given values n1 and n2 . This function assumes that n1 and n2 are present in Binary Tree ; 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 ; Driver program to test above functions
class Node { int data ; Node left , right ; public Node ( int item ) { data = item ; left = right = null ; } } public class BinaryTree { Node root ; Node findLCA ( int n1 , int n2 ) { return findLCA ( root , n1 , n2 ) ; } Node findLCA ( Node node , int n1 , int n2 ) { if ( node == null ) return null ; if ( node . data == n1 node . data == n2 ) return node ; Node left_lca = findLCA ( node . left , n1 , n2 ) ; Node right_lca = findLCA ( node . right , n1 , n2 ) ; if ( left_lca != null && right_lca != null ) return node ; return ( left_lca != null ) ? left_lca : right_lca ; } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 2 ) ; tree . root . right = new Node ( 3 ) ; tree . root . left . left = new Node ( 4 ) ; tree . root . left . right = new Node ( 5 ) ; tree . root . right . left = new Node ( 6 ) ; tree . root . right . right = new Node ( 7 ) ; System . out . println ( " LCA ( 4 , ▁ 5 ) ▁ = ▁ " + tree . findLCA ( 4 , 5 ) . data ) ; System . out . println ( " LCA ( 4 , ▁ 6 ) ▁ = ▁ " + tree . findLCA ( 4 , 6 ) . data ) ; System . out . println ( " LCA ( 3 , ▁ 4 ) ▁ = ▁ " + tree . findLCA ( 3 , 4 ) . data ) ; System . out . println ( " LCA ( 2 , ▁ 4 ) ▁ = ▁ " + tree . findLCA ( 2 , 4 ) . data ) ; } }