Find the first occurrence of k in a BST
SearchBSTForFirstOccurrenceRecursive.java
public static BinaryTree<Integer> findFirstEqualK(
BinaryTree<Integer> T, Integer k) {
if (T == null) {
return null; // No match.
} else if (T.getData().compareTo(k) == 0) {
// Recursively searches the left subtree for first one == k.
BinaryTree<Integer> n = findFirstEqualK(T.getLeft(), k);
return n != null ? n : T;
}
// Searches left or right tree according to T.getData() and k.
return findFirstEqualK(
T.getData().compareTo(k) < 0 ? T.getRight() : T.getLeft(), k);
}
SearchBSTForFirstOccurrenceIterative.java
public static BinaryTree<Integer> findFirstEqualK(
BinaryTree<Integer> T, Integer k) {
BinaryTree<Integer> first = null;
BinaryTree<Integer> curr = T;
while (curr != null) {
if (curr.getData().compareTo(k) < 0) {
curr = curr.getRight();
} else if (curr.getData().compareTo(k) > 0) {
curr = curr.getLeft();
} else { // curr.getData().compareTo(k) == 0
// Searches for the leftmost in the left subtree.
first = curr;
curr = curr.getLeft();
}
}
return first;
}
Find the first key larger than k in a BST
SearchBSTFirstLargerK.java
public static BinaryTree<Integer>
findFirstLargerKWithKExist(BinaryTree<Integer> r, Integer k) {
boolean foundK = false;
BinaryTree<Integer> curr = r;
BinaryTree<Integer> first = null;
while (curr != null) {
if (curr.getData().compareTo(k) == 0) {
foundK = true;
curr = curr.getRight();
} else if (curr.getData().compareTo(k) > 0) {
first = curr;
curr = curr.getLeft();
} else { // curr.getData().compareTo(k) < 0
curr = curr.getRight();
}
}
return foundK ? first : null;
}
Find the k largest elements in a BST FindKLargestBST.java
public static List<Integer> findKLargestInBST(
BinaryTree<Integer> root, int k) {
List<Integer> kElements = new ArrayList<>();
findKLargestInBSTHelper(root, k, kElements);
return kElements;
}
private static void findKLargestInBSTHelper(
BinaryTree<Integer> r, int k, List<Integer> kElements) {
// Performs reverse inorder traversal.
if (r != null && kElements.size() < k) {
findKLargestInBSTHelper(r.getRight(), k, kElements);
if (kElements.size() < k) {
kElements.add(r.getData());
findKLargestInBSTHelper(r.getLeft(), k, kElements);
}
}
}
Build a BST from a sorted array with minimum height BuildBSTFromSortedSortedArray.java
private static BinaryTree<Integer> buildBSTFromSortedArrayHelper(List<Integer> a, int start, int end) {
if (start < end) {
int mid = start + ((end - start) / 2);
return new BinaryTree<>(a.get(mid),
buildBSTFromSortedArrayHelper(a, start, mid),
buildBSTFromSortedArrayHelper(a, mid + 1, end));
}
return null;
}
Update a BST UpdateBST.java
Compute the average of the top three scores AverageTop3Scores.java
To save memory, we can save at most 3 scores for each student: when add scores, if there are already 3 scores, compare current score with least score in the map, if current score is bigger, remove the least one and add current score, otherwise ignore it.private static class UniqueInteger implements Comparable<UniqueInteger> {
public Integer value;
public Long sequence;
public UniqueInteger(Integer value, Long sequence) {
this.value = value;
this.sequence = sequence;
}
public int compareTo(UniqueInteger o) {
int result = value.compareTo(o.value);
if (result == 0) {
result = sequence.compareTo(o.sequence);
}
return result;
}
}
public static String findStudentWithTopThreeAverageScores(InputStream ifs) {
Map<String, TreeSet<UniqueInteger>> studentScores = new HashMap<>();
try {
long sequence = 0;
ObjectInputStream ois = new ObjectInputStream(ifs);
while (true) {
String name = ois.readUTF();
int score = ois.readInt();
TreeSet<UniqueInteger> scores = studentScores.get(name);
if (scores == null) {
scores = new TreeSet<>();
}
scores.add(new UniqueInteger(score, sequence++));
studentScores.put(name, scores);
}
} catch (IOException e) {
}
String topStudent = "no such student";
int currentTopThreeScoresSum = 0;
for (Map.Entry<String, TreeSet<UniqueInteger>> scores : studentScores
.entrySet()) {
if (scores.getValue().size() >= 3) {
int currentScoresSum = getTopThreeScoresSum(scores.getValue());
if (currentScoresSum > currentTopThreeScoresSum) {
currentTopThreeScoresSum = currentScoresSum;
topStudent = scores.getKey();
}
}
}
return topStudent;
}
// Returns the sum of top three scores.
private static int getTopThreeScoresSum(TreeSet<UniqueInteger> scores) {
Iterator<UniqueInteger> it = scores.iterator();
int result = 0;
for (int i = 0; i < 3 && it.hasNext(); i++) {
result += it.next().value;
}
return result;
}
Test if a binary tree is a min-first BST SearchMinFirstBST.java
public static boolean searchMinFirstBST(BinaryTree<Integer> T, Integer k) {
if (T == null || T.getData().compareTo(k) > 0) {
return false;
} else if (T.getData().compareTo(k) == 0) {
return true;
}
// Search the right subtree if the smallest key in the right subtree is
// greater than or equal to k.
if (T.getRight() != null && k.compareTo(T.getRight().getData()) >= 0) {
return searchMinFirstBST(T.getRight(), k);
}
return searchMinFirstBST(T.getLeft(), k);
}
