Binary Trees & the Genre Tree
Tunebox's genres aren't a flat list. Music splits into Rock and Electronic; Rock splits into Punk and Metal. A list can hold those names, but it can't say that Punk sits under Rock. A tree can — and once that shape is in memory, one short recursive function reaches every branch.
A node and its two children
A binary tree is made of nodes. Each holds a value and up to two children,
left and right; a missing child is None.
The top node is the root. A node with no children is a leaf — Punk, Metal, House. Every child starts its own subtree: a smaller tree that follows exactly the same rules. That is why recursion fits trees so well.
❓ Cross-question — "Why not a dict of lists,
{"Music": ["Rock", "Electronic"]}?" That's a fine general tree. A binary tree caps each node at two named slots, and the next lessons lean on that cap: a search tree keeps smaller keys left and bigger ones right, and a heap packs its nodes into a flat list by position.
Depth and height
Depth is a node's distance from the root: Music is depth 0, Punk depth 2. Height is how tall the tree is. We count nodes on the longest root-to-leaf path, so an empty tree has height 0 and a lone root height 1. (Some books count edges instead — one fewer. Check which one a problem means.)
Height is recursion in its purest form — a tree is one node taller than its taller subtree:
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
jazz = Node("Jazz", Node("Bebop", None, Node("Hard Bop")), Node("Swing"))
print(height(jazz))From a level-order list to a tree
Tunebox stores the genre tree as JSON, so it arrives level by level, left to
right, with None for a missing child:
["Music", "Rock", "Electronic", "Punk", "Metal", None, "House"]Read it with a queue. The first value is the root. After that, values come in pairs
— the left and right child of each real node, in the order the nodes were made. A
None has no children, so it never claims a pair of its own.
Every graded function in this section works this way: build the nodes from the list, work on real nodes, return plain values.
Depth-first: pre-, in- and post-order
A depth-first traversal dives all the way down one branch before trying the next. The three classic orders differ only in when the node itself is visited:
- pre-order — node, left, right. Parents before children, like a table of contents.
- in-order — left, node, right. In the next lesson's search trees, this is sorted order.
- post-order — left, right, node. Children before parents: sizes, totals, deletes.
Step through a pre-order walk and watch the calls go down and come back up:
Now move the append to the end:
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def postorder(node, out):
if node:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.val)
return out
root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(postorder(root, []))Coming from Java/JS: the recursion is the same —
if (node == null) return;becomesif node is None: return. Preferis Nonetoif not nodeonce values can be falsy, like0or"".
Breadth-first: level order with a deque
Level order visits the root, then every node at depth 1, then depth 2 — the same
queue trick build used. Take a node from the front, add its children to the back:
❓ Cross-question — "Why a
deque, notlist.pop(0)?"pop(0)shifts every remaining item left — O(n) per pop, O(n²) for the whole walk.deque.popleft()is O(1). You won't notice on seven genres; you will on a million-node tree.
Root-to-leaf paths
The genre browser needs every full path, like Music > Rock > Punk. Walk down
carrying the trail so far, and record it when you reach a leaf. The easy mistake is
sharing one trail list between every call and never taking anything back off it:
This should print both paths, but the second comes out as 'Music > Rock > Jazz' — Rock is still on the trail. Fix it.
There are two cures: trail.pop() after the recursive calls (that's
backtracking), or pass trail + [node.val] down so each call owns a copy.
| Operation | Time | Extra space |
|---|---|---|
| Build from a level-order list | O(n) | O(n) nodes |
| Pre-, in-, post-order (recursive) | O(n) | O(h) call stack |
| Level order with a deque | O(n) | O(w), the widest level |
| Height | O(n) | O(h) |
| All root-to-leaf paths | O(n · h) | O(n · h) for the strings |
h is the height: about log₂ n when the tree is bushy, but n when it's one long chain.
Idioms & real-world patterns
Depth-first without recursion
Swap the queue for a stack and you get pre-order. Push the right child first, so the left one is popped first:
Trees are everywhere once you look for them: folders on disk, the HTML DOM, and the
syntax tree Python builds from your own code, which the ast module hands you.
⚡ Advanced — when recursion runs out of stack
CPython stops recursing at about 1000 frames. A balanced tree of a million nodes is only ~20 levels deep, but a degenerate one — each node with a single child — is as deep as it is long:
For input you don't control, use the explicit stack or deque versions.
⚡ Advanced — a traversal as a generator
yield from turns a traversal into a lazy stream you can stop early:
🎯 Your turn
Write genre_paths(levels). levels is the genre tree as a level-order list with
None for a missing child. Return every root-to-leaf path joined with " > ",
left to right:
genre_paths(["Music", "Rock", "Electronic", "Punk", "Metal", None, "House"])→["Music > Rock > Punk", "Music > Rock > Metal", "Music > Electronic > House"]genre_paths([])→[]
Hint — the starter's build(levels) makes the nodes. Recurse with the trail so
far, and record it when a node has no children.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅