This last programming project is entirely dedicated to binary search trees. Your task is to fill in the implementation for three methods of the BinarySearchTree class in bst.scala, namely upperNeighbor, range, and split.
Do not change any of the existing methods. You can define new private methods, and you probably want to add a method that prints the tree in a nice way to help you debugging.
The public method range prepares a ListBuffer (a singly-linked list with fast append that can later be converted to a List in constant time) and calls the private method range. Fill in the implementation of this private method.
The method must run in time \(O(h)\), where \(h\) is the height of the tree. So you cannot simply collect the elements and build two new trees: You must compose the new trees from subtrees of the original tree.
I have already written the public method split, your task is to implement the private method split(x: Int, n: Node). It splits the subtree with root \(n\) and returns the roots of the two new trees. This can be done recursively: You need to create a new root node for one of the output trees, attach one of the subtrees of \(n\) to it, and recursively split the other subtree of \(n\). (There is also the special case x == n.key which can be handled without going into recursion.)
You can use treetest.scala to test your code (this is not a test suite, just run the object TreeTest). Here is an example output:
$ scala TreeTest 100 13 Inserting numbers into tree. Height of tree t is 12 Size of tree t is 99 Removing odd numbers from tree: Height of tree is 10 Size of tree t is 49 First key: 2, last key: 98 Testing that all numbers are in the map: Testing that numbers were deleted: Computing ranges: Range [-7,19] = List(2, 4, 6, 8, 10, 12, 14, 16, 18) Range [16,23] = List(16, 18, 20, 22) Range [345,123] = List() Range [93,105] = List(94, 96, 98) Upper neighbors: Upper(99) = No such neighbor Upper(98) = No such neighbor Upper(-7) = 2 Upper(15) = 16 Upper(64) = 66 Splitting: Splitting at 13: Left size: 6, height 3, max key: 12 Right size: 43, height 10, min key: 14 Splitting at -5: Left size: 0, height -1, max key: ? Right size: 49, height 10, min key: 2 Splitting at 50: Left size: 25, height 6, max key: 50 Right size: 24, height 7, min key: 52 Splitting at 98: Left size: 49, height 10, max key: 98 Right size: 0, height -1, min key: ? Splitting at 97: Left size: 48, height 10, max key: 96 Right size: 1, height 0, min key: 98