Binary Trees

A binary tree is a structure of nodes in which each node has at most two children and every node but the root has one parent. It matters because the search trees, heaps and tries that follow are all trees, and the ways of walking a tree and computing over it carry over to each of them. The topic starts with the parts of a tree and how depth and height are measured, then walks the three depth-first orders, which differ only in when a node is visited, and level order, which uses a queue. It then turns to the off-by-one that comes from counting height in nodes instead of edges, and to the pattern behind most tree functions: answer for the empty tree, then combine the two subtrees' answers. It ends with the traversals in three languages and an exercise on a knockout bracket.