The search operation is largely identical to searching in a regular binary search tree. Starting from the root, we search for the target value by moving down the tree such that:
- If the target value is less than the current node value and there is a node to the left of the current node, we call
- If the target value is greater than the current node value and there is a node to the right of the current node, we call
- If the target value is equal to the current node value, we are finished searching. Once the target value is found, we splay the found node to make it the root and return
Implement the logic outlined above within the
search() method. Make sure to avoid hitting an infinite loop with your while loop.