Skip to content

Instantly share code, notes, and snippets.

@anhnguyen1618
Created December 7, 2016 13:26
Show Gist options
  • Save anhnguyen1618/cb76307a02683a4c2f79577e7bcf4c6f to your computer and use it in GitHub Desktop.
Save anhnguyen1618/cb76307a02683a4c2f79577e7bcf4c6f to your computer and use it in GitHub Desktop.
static Node lca(Node root,int v1,int v2)
{
ArrayList<Node> list = new ArrayList<Node>();
helper(root,v1,v2, list);
return list.get(list.size()-1);
}
static Node helper(Node node,int v1,int v2,ArrayList<Node> array){
if(node.left == null && node.right == null){
return null;
}
if(isParent(node,v1)&&isParent(node,v2) ){
array.add(node);
}
if(node.left != null){
helper(node.left,v1,v2, array);
}
if(node.right != null) {
helper(node.right,v1,v2, array);
}
return null;
}
static boolean isParent(Node node, int v1){
if(node.left == null && node.right == null){
return false;
}
if(node.data == v1){
return true;
}
boolean hasLeft = false;
boolean hasRight = false;
if(node.left != null){
hasLeft = isParent(node.left,v1);
}
if(node.right != null){
hasRight = isParent(node.right,v1);
}
return hasLeft || hasRight;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment