Although binary search trees have the potential to be more efficient than ordered arrays and linked lists, they are only efficient if they are balanced.

Therefore, your task is now to update your implementation so that it uses a height$-$balanced binary search tree.