Module 62 Extra

Trees and heaps

Trees and the recursion that walks them. Binary trees and linked lists, binary search trees, the three traversals, stacks and level order with a deque, with what each costs and where a deep tree breaks recursion. Then binary heaps, by hand and with heapq, and tries for prefix search. Big tests show where a heap, a balanced tree or a trie is the fast way.

Steps

1. Binary trees and recursion
2. Binary search trees
3. Traversals and validation
4. Level order with a deque
5. Heaps and heapq
6. Challenge: tries