What you'll learn
A tree is a hierarchy: a root node with children, each of which is itself a little tree. Unlike a list, there's no single "next" — so visiting every node takes a strategy. There are four, and this module animates all of them.
By the end you'll be able to:
- Use the core tree vocabulary: root, parent, child, leaf, height, depth
- Perform the three depth-first traversals: pre-, in-, and post-order
- Perform a breadth-first (level-order) traversal with a queue
Tree terminology
| Term | Meaning |
|---|---|
Root | The top node, with no parent |
Parent / Child | A node directly above / below another |
Leaf | A node with no children |
Height | Longest path from a node down to a leaf |
Depth / Level | Distance from the root down to a node |
Subtree | Any node together with all its descendants |
A binary tree restricts each node to at most two children (left and right) — the shape behind BSTs, heaps, and expression trees.
Depth-first traversals
Depth-first traversal dives as deep as possible before backing up — naturally recursive. The only difference between the three is when you visit the node relative to its subtrees. Watch the same tree, three orders:
Breadth-first traversal
Level-order visits the tree row by row, top to bottom. It's not recursive — it uses a queue (Module 8): dequeue a node, visit it, enqueue its children. This is exactly BFS, which we'll see again on graphs.
In code
def preorder(node):
if node:
visit(node) # node FIRST
preorder(node.left)
preorder(node.right)
def inorder(node):
if node:
inorder(node.left)
visit(node) # node in the MIDDLE
inorder(node.right)
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
visit(node) # node LAST
def level_order(root): # breadth-first with a queue
q = deque([root])
while q:
node = q.popleft()
visit(node)
if node.left: q.append(node.left)
if node.right: q.append(node.right)Key idea
visit() moved. Depth-first uses the call stack; breadth-first uses an explicit queue.Recap & quick check
Key takeaways
- A tree is a hierarchy of nodes; a binary tree allows at most two children per node.
- Depth-first traversal is recursive; the visit position gives pre-, in-, or post-order.
- In-order traversal of a BST yields sorted order.
- Breadth-first (level-order) uses a queue to go row by row.
- All four visit every node once: O(n) time.
Quick check
1. Which traversal visits the node between its left and right subtrees?
2. Level-order (breadth-first) traversal uses which structure?
3. Post-order traversal visits a node:
4. How many nodes does any full traversal visit, for a tree of n nodes?
Traversals visit a tree; next we make the tree searchable and keep it that way. Next up: Module 17 — Binary Search Trees.