Interview Question
Country: United States
The solution provided here assume that there is a parent pointer, but it's a working solution. +1
If there are no parent pointers;
LCA(A, B)
1. Get inorder list from (A, B).
1.2. If there are no elements between inorder (A, B), then return the latter
1.3 else
1.3.a. Check the order of each element in (A,B) in post-order
1.3.b. Return the highest order element in postorder, which is the LCA
e.g., LCA(10, 40)
inorder : 10 20 30 40 80
postorder : 10 30 20 80 40
then LCA(10, 40) = 20
O(n) time, O(n) space
public boolean isAncestor(Node ancestor, Node child) {
if(ancestor == null || child == null) {
return false;
}
Node parent = child;
while(parent != null) {
if(parent = ancestor) {
return true;
}
parent = parent.getParent();
}
return false;
}
public Node getCommonAncestor(Node node1, Node node2) {
if(isAncestor(node1, node2)) {
return node1;
} else if(isAncestor(node2, node1)) {
return node2;
} else {
if(node1 == null || node2 == null) {
return null;
} else {
Node parent = node1.getParent();
while(parent != null) {
if(isAncestor(parent, node2)) {
return parent;
}
parent = parent.getParent();
}
return null;
}
}
}
Assuming that we have nodes containing info1 and info2 present inside the BST
public BTreeNode<T> leastCommonParent(BTreeNode<T> node,T info1,T info2){
BTreeNode<T> node1 = new BTreeNode<T>(info1);
BTreeNode<T> node2 = new BTreeNode<T>(info2);
//return null if node==null
if(node==null){
return null;
}
if(node.getLeft()!=null){
if(node.getLeft().compareTo(node1)==0 || node.getLeft().compareTo(node2)==0){
return node;
}
}
if(node.getRight() !=null){
if(node.getRight().compareTo(node1)==0 || node.getRight().compareTo(node2)==0){
return node;
}
}
if(node.compareTo(node1)>0 && node.compareTo(node2)>0){
return leastCommonParent(node.getLeft(), info1, info2);
//return node;
}
else if(node.compareTo(node1)<0 && node.compareTo(node2)<0){
return leastCommonParent(node.getRight(), info1, info2);
}else{
return node;
}
}
- coding.arya August 07, 2013int Depth(Node* n1) { int depth = 0; while (n1->parent) { ++depth; n1 = n1->parent; } return depth; } Node* CommonAncestor(Node* n1, Node* n2) { int d1 = Depth(n1); int d2 = Depth(n2); if (d1 > d2) { while (d1 != d2) { --d1; n1 = n1->parent; } } else if (d2 > d1) { while (d1 != d2) { --d2; n2 = n2->parent; } } //Now they are on same level... while (n1 != n2) { n1 = n1->parent; n2 = n2->parent; } return n1; //or n2 }