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:

An input of 13 results in 52

An input of 67 results in 68

An input of 55 results in 67

An input of 5 results in 10

An input of 83 results in Optional.empty

An input of 100 results in Optional.empty

Any input on an empty binary tree results in Optional.empty

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

Implement the following method, provided in the InOrderSuccessorBinaryTree class that extends the SimpleBinaryTree class.

public Optional inOrderSuccessorKey(K key)

Steps for Completion

Use a non-recursive search operation first to find the first node with a key equal to or less than the input.

Realize that the inorder successor can be in only one of two places, either as a parent of this node or the minimum key on the subtree of the right child of this node (if any).

Grading

Complete each task listed below. Each task contains automated checks which are used to calculate your grade. When you have completed each task by clicking the checkbox, open the task list panel on the left navigation bar and click the "Submit" button.

Task

Use a non-recursive search operation to retrieve the successor element when traversing a tree in order.

Code Given:

import java.util.Optional;

public class InOrderSuccessorBinaryTree extends SimpleBinaryTree { public Optional inOrderSuccessorKey(K key) { return null; } }