/*
find the first node with value above K in a binary search tree
*/
public class EdgeFindOne {
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);
int k = 15;
System.out.println("the first node with value above " + k);
System.out.println(largerThan(root, k));
k = 6;
System.out.println("the first node with value above " + k);
System.out.println(largerThan(root, k));
k = -6;
System.out.println("the first node with value above " + k);
System.out.println(largerThan(root, k));
k = -5;
System.out.println("the first node with value above " + k);
System.out.println(largerThan(root, k));
k = 1000;
System.out.println("the first node with value above " + k);
System.out.println(largerThan(root, k));
}
public static BTree largerThan(BTree root, int k) {
if(root == null) return null;
BTree l = largerThan(root.left, k);
if(l != null) {
return l;
}
if(root.value > k) return root;
return largerThan(root.right, k);
}
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;
}
}
