The binary search tree. A classic when it comes to learning about trees.

The thing about them

They are not some new ds that we haven't seen, they are specifically an ordering to the data within the data structure.

Lets program them, but first whiteboard the algorithm

  • Find
    • Running time?
  • Insertion
    • what does this do to running time?
  • Deletion
    • Trickier than you thought? O Y E S

  • Just the search part (its super easy)

Lets compare

Binary search an array vs a tree?

  • What feels easier to implement?