Binary Trees and the Recursive Mind-Shift

Hook #

Until now, the data structures you've built have been flat. Arrays are a row of values; linked lists are a chain. You walk them with a loop. Trees break that pattern in a specific way: a tree node holds values and other tree nodes, and the natural way to walk one is not a loop — it's a function that calls itself. This lesson is about the shift from iterative-over-flat-data to recursive-over-nested-data. Almost every interesting data structure in the second half of this curriculum — BSTs, heaps, B-trees, file systems, syntax trees, scene graphs, DOM — is a tree. The shift you make in this lesson is the one you use for the next thirty years.

What you'll be able to do by the end of this lesson #

• Define a binary tree as a recursive ADT in 3 lines of pseudo-type-signature.
• Write the size, height, and "contains-x" operations on a binary tree using structural recursion (not loops, not stacks).
• Trace inorder, preorder, postorder, and level-order traversals on the same small tree and predict their outputs.
• Recognise three real systems that are binary trees: BSTs, heaps, ASTs.

A quick try before we start #

Here is a tree of 7 integers:

text        5
       / \
      3   8
     / \   \
    1   4   9
             \
              11

Without coding anything, write down what size(tree) should return, what height(tree) should return (in number of edges from root to deepest leaf), and the inorder traversal (read left subtree, then node, then right subtree, recursively).

If those three answers come to you in less than a minute, you already have part of what this lesson is teaching. If they don't, that's fine — they will by the end.

The core idea, from first principles #

A binary tree is one of two things:

1. Empty (no nodes at all), or
2. A node holding a value, a left subtree, and a right subtree.

That's it. Two cases. The whole definition fits in three lines:

textBinaryTree<T> = Empty | Node(value: T, left: BinaryTree<T>, right: BinaryTree<T>)

The thing that makes this hard the first time is the self-reference: a binary tree contains binary trees. It's a recursive type. The pedagogical mind-shift is that this is fine — in fact, it's exactly the right shape, because it lets us write every operation on a binary tree as two clauses: one for empty, one for node. The recursive structure of the type drives the recursive structure of the algorithm. This pattern has a name: structural recursion.

Let's see it. Here's size (count the number of nodes):

rubydef size(tree)
  return 0 if tree.nil?           # empty case
  1 + size(tree.left) + size(tree.right)  # node case
end

Read it. The empty case returns 0 — there are no nodes in an empty tree. The node case returns one (for the current node) plus the size of the left subtree plus the size of the right subtree. The recursion mirrors the type definition: empty maps to the base case; node maps to the recursive case.

Now height (longest path from this node to any leaf, counted in edges):

rubydef height(tree)
  return -1 if tree.nil?          # empty case: height is -1 (so leaf height = 0)
  1 + [height(tree.left), height(tree.right)].max
end

Same shape. Empty case returns a base value; node case combines the recursive results. The choice of -1 for empty isn't arbitrary — it makes a single leaf (whose left and right subtrees are both empty) have height 1 + max(-1, -1) = 0, which is the convention.

Now contains?(x):

rubydef contains?(tree, x)
  return false if tree.nil?
  return true if tree.value == x
  contains?(tree.left, x) || contains?(tree.right, x)
end

Three cases instead of two — empty, found, recurse. The recursive structure is doing the work for you. You aren't tracking which node to visit next; the call stack tracks it (Course 2.1 lesson 4 connects directly here). You aren't writing a loop; the recursion is the loop.

This is the mind-shift. Recursion isn't a clever trick — it's the right shape for recursive data. When you write size as a loop with a manual stack of nodes to visit, you are re-implementing what recursion does for free. Sometimes you have to (Python's recursion-limit, real-time systems, memory constraints), but the recursive version is the version you understand first, then translate down if you must.

The four traversals are four orderings of one recursion #

Every traversal of a binary tree does the same three things at every node: visit the node, recurse left, recurse right. The four named traversals differ only in the order of those three actions:

Three of those four are the same function with the print statement moved:

rubydef preorder(tree)
  return if tree.nil?
  puts tree.value          # visit
  preorder(tree.left)      # left
  preorder(tree.right)     # right
end

def inorder(tree)
  return if tree.nil?
  inorder(tree.left)       # left
  puts tree.value          # visit
  inorder(tree.right)      # right
end

def postorder(tree)
  return if tree.nil?
  postorder(tree.left)     # left
  postorder(tree.right)    # right
  puts tree.value          # visit
end

That's it. Three traversals, one structural-recursion pattern, three different placements of the visit step. Once you see this, you stop memorising "what does inorder do?" and start deriving it from the placement of the recursive call.

Level-order is the odd one out — it requires a queue (Course 2.1 lesson 5) and is iterative by nature. The other three are recursive by nature. The structural distinction matters: depth-first traversals (preorder, inorder, postorder) use the call stack; breadth-first (level-order) uses an explicit queue. That's the same stack/queue duality you saw in the previous course, applied to trees.

For the tree in the "quick try" above, the answers are: size = 7, height = 3, and inorder = 1, 3, 4, 5, 8, 9, 11 (which is sorted — not a coincidence; we'll see why in the BST lesson).

Why this works the way it does #

The deep reason structural recursion works: the type definition and the algorithm have the same shape. If your data has N cases (here, 2: empty and node), your function has N clauses. If your data refers to itself recursively, your function calls itself recursively at the same recursion sites. The compiler can mechanically check that you've handled every case (in languages with pattern matching, this is enforced). In Ruby, you check by hand — but the discipline is the same: every recursive type gets a function with one clause per type case.

This is called the principle of structural recursion and it's a direct application of mathematical induction — which you already saw in Course 1.1 (proof techniques). The base case of induction matches the base case of the recursion (empty tree). The inductive step matches the recursive case (assuming we can size both subtrees, we know how to size the whole). The proof of correctness is the recursion, written out as math. You're already doing inductive reasoning every time you write a recursive tree function; you just may not have noticed.

The other deep reason: trees are the simplest recursive data structure that isn't a list. A linked list (Course 2.1 lesson 2) is Empty | Node(value, next: List) — one recursive reference. A binary tree is Empty | Node(value, left: Tree, right: Tree) — two recursive references. An n-ary tree generalises to n references. A graph generalises further (a node can reference any other node). Each step up the ladder is more expressive and more complex; the binary tree is where you train the recursive-thinking habit you'll spend the rest of CS using.

Explain it back to me #

A junior engineer asks: "Why does the size function on a binary tree not need a loop? Don't we have to visit every node?"

In your own words, answer in two sentences. Use the words "recursion" and "structural" and "call stack."

And one follow-up: a friend writes preorder and postorder and says they're the same algorithm because they both visit every node. You disagree. Name one situation where the order matters — i.e., a problem where preorder gives the right answer and postorder gives the wrong one (or vice versa).

A small exercise #

For each, write a single recursive function on a binary tree:

1. leaf_count(tree) — return the number of leaves (nodes with no children).
2. mirror(tree) — return a new tree that is the mirror image (swap left and right at every node).
3. is_balanced?(tree) — return true if, at every node, the heights of the left and right subtrees differ by at most 1.

Where this connects #

Backward: Course 1.1 lesson 3 (Proof Techniques) introduced mathematical induction. Structural recursion is induction in code. Course 1.2 lesson 4 (Recurrences) gave you the tools to analyse recursive functions' running time — for a balanced binary tree of n nodes, size(tree) = T(n/2) + T(n/2) + O(1) = O(n) by the master theorem, which is the analysis you should now be able to do in your head. Course 2.1 lesson 4 (Stacks) is what's underneath your recursive calls — the call stack literally is the data structure managing your tree traversal.

Forward: Lesson 2 (BSTs) takes binary trees and adds an ordering invariant — left subtree values are less than the node, right subtree values are greater. Lesson 5 (Heaps) takes binary trees and adds a heap-order invariant — parent is always less than (or greater than) its children. Course 2.5 (Graphs) takes trees and generalises to arbitrary node-references. Course 13.x (Compilers) uses trees as the representation of code — an Abstract Syntax Tree is exactly the recursive ADT you wrote above, where the value at each node is a token and the children are the operands. The zc-bst-visualizer project (later in this course) has you build a small renderer for BSTs — applying everything in this lesson to a visible artifact.