Beginning Java Data Structures and Algorithms

Activity: Retrieving the Successor of an Element When the Tree is Traversed in Inorder

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 ...