Binary trees & recursive shape

A binary tree is defined by recursion: a node is {value, left, right}, and a subtree is either another node or nil. Every function over a tree follows that definition — handle nil as the base case, and handle a node by combining the results from its two subtrees. Size, height, and sum are the same recursion with a different combine step.

Because the data branches, the recursion branches too: two recursive calls per node instead of the one a list needed. Select a function to see its clauses and result over the seven-node tree.

Functions that fold a tree Advanced: structural sharing

Functions that fold a tree

Each function has a clause for nil and a clause for a node. The node clause makes two recursive calls — one per subtree — and combines them. Select one and read its clauses and result.

The function · select one

clause: size({v, l, r}) = 1 + size(l) + size(r)

result: 7 · base: size(nil) = 0

There are always exactly two clauses to get right: what an empty tree is worth, and how to fold a node from its two subtrees. Miss neither and the function is total — the recursion cannot run off the end.

Advanced: structural sharing on insert

Trees are immutable here, so insert returns a new tree — but it does not copy the old one. It rebuilds only the nodes on the path from the root to the new leaf and shares every untouched subtree by reference. Inserting 15 walks 12 → 30 → 20 and hangs it on 20’s empty left, so three nodes are rebuilt and the entire left half of the tree is shared unchanged.

insert(tree, 15) · rebuilt path vs shared subtrees

Three nodes rebuilt on the path, one new leaf, four subtrees shared by reference. For a balanced tree that is O(log n) new nodes per insert — the foundation of persistent data structures, and exactly how the tries later in this chapter stay cheap to update.

def insert(nil, x), do: {x, nil, nil}
def insert({v, l, r}, x) when x < v, do: {v, insert(l, x), r}
def insert({v, l, r}, x) when x > v, do: {v, l, insert(r, x)}
def insert({v, l, r}, _x), do: {v, l, r}   # already present

The idea

Solve a node by combining the answers from its two subtrees — and on insert, copy only the path you change.

In Elixir

f({v, l, r}) = combine(v, f(l), f(r)), with nil as the base; insert shares the rest.

Next: depth-first traversals — the order in which you combine the subtrees gives pre-, in-, and post-order.

References

Primary sources for this lesson, and where it connects in the course.

Sources

Tree traversal — Wikipedia — depth-first and breadth-first orders.
Okasaki, C. (1996). Purely Functional Data Structures. — trees, functionally.