QUESTION
Scenario
We need to write a method that, given a key as an argument, returns the next in order key found in the binary search tree. If the key given as an argument is not found, the method should still return the next in order key. If the binary tree is empty or all the stored keys are smaller than the argument, then the return value should be empty.
For example, using a collection of {10,13,52,67,68,83} stored in the binary search tree:
Both the in order successor and predecessor algorithms have many applications. As an example, think about if you had to keep a scoreboard at some sports event where you only want to show the first three runners. If you keep your data in a binary search tree, you can find the maximum key and then work out the next two predecessor nodes.
The solution needs to have a runtime complexity of O(log n).
Aim
Retrieve the successor of an element when the tree is traversed in inorder.
Prerequisites
public Optional<K> inOrderSuccessorKey(K key)
Steps for Completion
Task
Use a non-recursive search operation to retrieve the successor element when traversing a tree inorder.
InOrderSuccessorBinaryTree.java
import java.util.Optional;
public class InOrderSuccessorBinaryTree<K,V> extends
SimpleBinaryTree<K,V> {
public Optional<K> inOrderSuccessorKey(K key) {
return null;
}
}
I need help with this please?