http://elementsofprogramminginterviews.com/solutions/
private static <T> int getDepth(BinaryTree<T> n) {
int d = 0;
while (n != null) {
++d;
n = n.getParent();
}
return d;
}
public static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
int depthI = getDepth(i), depthJ = getDepth(j);
if (depthJ > depthI) {
BinaryTree<T> temp = i;
i = j;
j = temp;
}
// Advance deeper node first.
int depthDiff = Math.abs(depthI - depthJ);
while (depthDiff-- > 0) {
i = i.getParent();
}
// Both pointers advance until they found a common ancestor.
while (i != j) {
i = i.getParent();
j = j.getParent();
}
return i;
}
public static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
HashSet<BinaryTree<T>> hash = new HashSet<BinaryTree<T>>();
while (i != null || j != null) {
if (i != null) {
if (hash.add(i) == false) {
return i; // adds a failed because a exists in hash.
}
i = i.getParent();
}
if (j != null) {
if (hash.add(j) == false) {
return j; // adds a failed because a exists in hash.
}
j = j.getParent();
}
}
// Throw error if a and b are not in the same tree.
throw new RuntimeException("a and b are not in the same tree");
}
Compute the LCA in a binary tree LowestCommonAncestorNoParentTemplate.java
public static <T> BinaryTree<T> LCA(BinaryTree<T> n, BinaryTree<T> a,
BinaryTree<T> b) {
if (n == null) { // empty subtree.
return null;
} else if (n == a || n == b) {
return n;
}
BinaryTree<T> lRes = LCA(n.getLeft(), a, b), rRes = LCA(n.getRight(), a, b);
if (lRes != null && rRes != null) {
return n;
} else {
return lRes != null ? lRes : rRes;
}
}
int d = 0;
while (n != null) {
++d;
n = n.getParent();
}
return d;
}
public static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
int depthI = getDepth(i), depthJ = getDepth(j);
if (depthJ > depthI) {
BinaryTree<T> temp = i;
i = j;
j = temp;
}
// Advance deeper node first.
int depthDiff = Math.abs(depthI - depthJ);
while (depthDiff-- > 0) {
i = i.getParent();
}
// Both pointers advance until they found a common ancestor.
while (i != j) {
i = i.getParent();
j = j.getParent();
}
return i;
}
Compute the LCA, optimizing for close ancestors
LowestCommonAncestorHashTemplate.javapublic static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
HashSet<BinaryTree<T>> hash = new HashSet<BinaryTree<T>>();
while (i != null || j != null) {
if (i != null) {
if (hash.add(i) == false) {
return i; // adds a failed because a exists in hash.
}
i = i.getParent();
}
if (j != null) {
if (hash.add(j) == false) {
return j; // adds a failed because a exists in hash.
}
j = j.getParent();
}
}
// Throw error if a and b are not in the same tree.
throw new RuntimeException("a and b are not in the same tree");
}
Find the k largest elements in a BST FindKLargestBST.java
public static BinaryTree<Integer> findLCA(
BinaryTree<Integer> x, BinaryTree<Integer> s, BinaryTree<Integer> b) {
BinaryTree<Integer> p = x;
while (p.getData() < s.getData() || p.getData() > b.getData()) {
while (p.getData() < s.getData()) {
p = p.getRight(); // LCA must be in p's right child.
}
while (p.getData() > b.getData()) {
p = p.getLeft(); // LCA must be in p's left child.
}
}
// p.getData() >= s.getData() && p.getData() <= b.getData().
return p;
}
