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:

• 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

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

public Optional<K> inOrderSuccessorKey(K key)

Steps for Completion

1. Use a non-recursive search operation first to find the first node with a key equal to or less than the input.
2. 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).

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;
}
}

Answer 1

Solution

Screenshot

import java.util.Optional;

public class InOrderSuccessorBinaryTree<K, V> extends SimpleBinaryTree<K, V> {
public Optional<K> inOrderSuccessorKey(K key) {
Optional<BinaryTreeNode<K, V>> node = Optional.ofNullable(root);
Optional<K> successor = Optional.empty();
while (node.isPresent() && !node.get().getKey().equals(key)) {
if (((Comparable) node.get().getKey()).compareTo(key) > 0) {
successor = node.map(BinaryTreeNode::getKey);
node = node.flatMap(BinaryTreeNode::getLeft);
} else
node = node.flatMap(BinaryTreeNode::getRight);
}

return node.flatMap(BinaryTreeNode::getRight).map(this::minKey)
.map(Optional::of).orElse(successor);
}
}

--

all the best