/*
find the closest common parent of 2 nodes in a tree
*/
public class GlobalOptimumThree {
public static void main(String...arg) {
int[] values = {10, -5, -20, 3, -15, 7, 26, -9, 14};
System.out.println("Layer order");
BTree root = buildTree(values);
BTreePrinter.printNode(root);
System.out.println("the common parent of 3, -9 is:");
System.out.println(commonParent0(root, 3, -9));
}
public static BTree commonParent0(BTree root, int start, int end) {
BTree parent = commonParent(root, Math.min(start, end), Math.max(start, end));
if(contains(parent, start) && contains(parent, end)) {
return parent;
}
return null;
}
public static BTree commonParent(BTree root, int start, int end) {
if(root == null) {
return null;
}
if(root.value >= start && root.value <= end) {
return root;
}
if(root.value > end) {
return commonParent(root.left, start, end);
}
if(root.value < start) {
return commonParent(root.right, start, end);
}
return root;
}
public static boolean contains(BTree root, int value) {
if(root == null) return false;
if(root.value == value) return true;
return contains(root.left, value) || contains(root.right, value);
}
//build a binary search tree
public static BTree buildTree(int[] values) {
BTree root = null;
for(int value : values) {
root = insert(root, value);
}
return root;
}
public static BTree insert(BTree root, int value) {
if(root == null) {
return new BTree(value, null, null);
}
if(value > root.value) {
root.right = insert(root.right, value);
return root;
}
if(value < root.value) {
root.left = insert(root.left, value);
return root;
}
root.value = value;
return root;
}
}
