Created
December 22, 2014 00:34
-
-
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 )
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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