Skip to content

Instantly share code, notes, and snippets.

@arjunrao87
Created December 22, 2014 00:34
Show Gist options
  • Save arjunrao87/41c1a7dd8b986d590085 to your computer and use it in GitHub Desktop.
Save arjunrao87/41c1a7dd8b986d590085 to your computer and use it in GitHub Desktop.
Find least common ancestor for 2 nodes a, b in a binary tree ( not BST )
public Node getLCA( Node node, int a, int b ){
if( node == null ){
return node;
}
if( node.getData() == a || node.getData() == b ){
return node;
}
Node lcaInLeft = getLCA( node.getLeft(), a, b );
Node lcaInRight = getLCA( node.getRight(), a, b );
if( lcaInLeft != null && lcaInRight != null ){
return node;
}
if( lcaInLeft == null && lcaInRight != null){
return lcaInRight;
}
if( lcaInLeft != null && lcaInRight == null){
return lcaInLeft;
}
if( lcaInLeft == null && lcaInRight == null){
return null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment