In order to practice implementing symbol tables, you will implement a binary search tree. A BST can

actually be considered to be another type of data structure that we can use to implement an ADT. Since

symbol tables are about nding values based on keys $($the search problem$),$ it's appropriate to use a BST to

implement them. BSTs are nice structures for searching, because they mimic the process of a binary search

$($O$($logn$)).$ Unfortunately, fast O$($logn$)$ look ups only work in BSTs that are balanced. Any time we remove

or add nodes, there is a chance the tree will become stilted, which can degrade search to look like O$($n$).$

After we nish the implementation of a BST$,$ we will go on to address this problem