Paul's Python CoursePPC

Binary search trees

Not met yet

A binary search tree keeps everything down a card's left side smaller than it and everything down its right side bigger. Finding a number walks down from the root, going left or right at each card, so it looks at one card per level. Adding is the same walk; the new card goes in the empty place where the walk ends. Filed in a jumbled order the tree stays bushy, about log n levels; filed in order it becomes a stick n levels high, and searching it is no better than a list.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks a binary search tree stays bushy whatever order the cards are added in, so a search always takes about log n looks.
  • Thinks searching a binary search tree has to look down both sides of a card, rather than only the side the number belongs on.
  • Thinks a new card goes in at the top of a binary search tree, pushing the others down, rather than at the empty place its walk ends.

Where it comes up