Lowest Common Ancestor in a Binary Tree | Set 1 | Class containing left and right child of current node and key ; Root of the Binary Tree ; 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 ; Store result in temp , in case of key match so that we can search for other key also . ; 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 ; Finds lca of n1 and n2 under the subtree rooted with ' node ' ; 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
class Node { int data ; Node left , right ; public Node ( int item ) { data = item ; left = right = null ; } } public class BinaryTree { Node root ; static boolean v1 = false , v2 = false ; Node findLCAUtil ( Node node , int n1 , int n2 ) { if ( node == null ) return null ; Node temp = null ; if ( node . data == n1 ) { v1 = true ; temp = node ; } if ( node . data == n2 ) { v2 = true ; temp = node ; } Node left_lca = findLCAUtil ( node . left , n1 , n2 ) ; Node right_lca = findLCAUtil ( node . right , n1 , n2 ) ; if ( temp != null ) return temp ; if ( left_lca != null && right_lca != null ) return node ; return ( left_lca != null ) ? left_lca : right_lca ; } Node findLCA ( int n1 , int n2 ) { v1 = false ; v2 = false ; Node lca = findLCAUtil ( root , n1 , n2 ) ; if ( v1 && v2 ) return lca ; return null ; } 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 ) ; Node lca = tree . findLCA ( 4 , 5 ) ; if ( lca != null ) System . out . println ( " LCA ( 4 , ▁ 5 ) ▁ = ▁ " + lca . data ) ; else System . out . println ( " Keys ▁ are ▁ not ▁ present " ) ; lca = tree . findLCA ( 4 , 10 ) ; if ( lca != null ) System . out . println ( " LCA ( 4 , ▁ 10 ) ▁ = ▁ " + lca . data ) ; else System . out . println ( " Keys ▁ are ▁ not ▁ present " ) ; } }