Card 08/ 08
Recap: Binary Trees
Three recursive orders, one queue for levels, heights in edges, and two results combined.
Binary trees come down to the six ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| Each node has at most two children and one parent, and every node is the root of its own subtree | Binary Trees: Nodes With at Most Two Children |
| Pre-order, in-order and post-order differ only in where the visit falls relative to the two subtrees | Traverse a Binary Tree in Pre-, In- and Post-Order |
| A queue gives level order: visit the front, add its children to the back, left first | Traverse a Binary Tree Level by Level |
Height counted in edges gives a leaf 0 and the empty tree -1; counted in nodes, each is one more | Counting Height in Nodes Instead of Edges |
| A tree function answers for the empty tree, then combines its two subtrees' answers with the node | Tree Functions Combine Two Recursive Results |
| Every traversal is O(n) time; recursion needs room for the height, a queue for the widest level | Binary Tree Traversals in Python, Java and TypeScript |
The four traversals visit the same nodes and differ in what each one knows at the moment of a visit. The second table sets them side by side on the tree used throughout this topic, with the structure behind each and a typical use. The three depth-first orders share one recursive function and change only where the visit goes, while level order needs a queue in place of the call stack.
| Order | Visits a node | On the topic's tree | Suits |
|---|---|---|---|
| Pre-order | Before both subtrees | 1 2 4 5 3 6 7 | Copying a tree, printing an outline |
| In-order | Between the subtrees | 4 2 5 1 3 7 6 | Sorted output from a binary search tree |
| Post-order | After both subtrees | 4 5 2 7 6 3 1 | Results that need the children first, such as height or deleting |
| Level order | When it reaches the front of the queue | 1 2 3 4 5 6 7 | Anything done one level at a time |
Together they let you write down any traversal of a binary tree by hand, measure height and depth without an off-by-one error, and write a recursive function that computes a tree's answer from its two subtrees.
← → move through sections and cards