19. Binary Trees

A binary tree is nodes with up to two children. Almost every tree solution is recursion: solve for the left subtree, solve for the right subtree, combine at the node. Ask yourself what each call should return (a height, a sum, a node, a pair of values).

Traversals decide when you visit the node. Preorder is node, left, right. Inorder is left, node, right. Postorder is left, right, node. Level order (BFS with a queue) goes row by row and is used for views and widths.