Problem
Given a binary search tree, f = (max + min)/2. Design an algorithm, find the value closest to f but larger than f. For example. In the following BST.
4
/ \
2 6
/ \ / \
1 3 5 7
f = (1 + 7)/2 = 4, the value closest to 4 and larger than 4 is 5.
Solution
we can call bst.min() and bst.max() to find the f. Then we call bst.floor(f) to find the value closest to f but larger than f. It is not floor though, there is one line difference, when root.value == f, we return min(root.right) instead of f.
class LargerThanMiddle {
public static Node largerThan(Node root, int f) {
if(root.value == f) {
return min(root.right);
} else if(root.value < f) {
return largerThan(root.right, f);
} else {
Node t = largerThan(root.left, f);
if(t == null) {
return root;
}
return t;
}
}
public static Node min(Node root) {
if(root == null)
return null;
if(root.left != null)
return min(root.left);
else
return root;
}
public static Node max(Node root) {
if(root == null) return null;
if(root.right != null)
return max(root.right);
else
return root;
}
public static void main(String...args) {
Node root = new Node(4,
new Node(2, new Node(1, null, null), new Node(3, null, null)),
new Node(6, new Node(5, null, null), new Node(7, null, null))
);
int f = (min(root).value + max(root).value)/2;
System.out.println(largerThan(root, f).value);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
public static Node largerThan(Node root, int f) {
if(root.value == f) {
return min(root.right);
} else if(root.value < f) {
return largerThan(root.right, f);
} else {
Node t = largerThan(root.left, f);
if(t == null) {
return root;
}
return t;
}
}
public static Node min(Node root) {
if(root == null)
return null;
if(root.left != null)
return min(root.left);
else
return root;
}
public static Node max(Node root) {
if(root == null) return null;
if(root.right != null)
return max(root.right);
else
return root;
}
public static void main(String...args) {
Node root = new Node(4,
new Node(2, new Node(1, null, null), new Node(3, null, null)),
new Node(6, new Node(5, null, null), new Node(7, null, null))
);
int f = (min(root).value + max(root).value)/2;
System.out.println(largerThan(root, f).value);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
The time cost will be O(logN) on average and O(N) at worst and extra space is O(logN).
