Guys, How about the below mentioned implementation?
The only assumptions is that nodes should exist in the tree. (will fail if
one node exists and another doesn't)
static Node LCA(Node root, int d1, int d2){
if(root==null)
return root;
if(root.left!=null && ( root.left.data == d1 || root.left.data==d2 ) )
// both nodes exists in left sub-tree
return root;
if(root.right!=null && ( root.right.data == d1 || root.right.data==d2) )
// both nodes exists in right sub-tree
return root;
Node ltree = LCA(root.left, d1, d2); //check recursively in left
subtree
Node rtree = LCA(root.right, d1, d2); // check recursively in
right subtree
if(ltree!=null && rtree!=null) // One node in left & another in right
return root;
return (ltree==null)?rtree:ltree;
}
Just to mention that, closest ancestor of 5&4 OR 4&9 would be 3 in the
following tree:
3
\
4
/ \
5 8
/
9
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/24JUUQsBHvIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
