Tree Properties

Basic measures

Three functions characterise the size and shape of a binary tree:

count — the number of branch (Br) nodes:

let rec count = function
  | Lf -> 0
  | Br (v, t1, t2) -> 1 + count t1 + count t2

depth — the length of the longest path from root to a leaf:

let rec depth = function
  | Lf -> 0
  | Br (v, t1, t2) -> 1 + max (depth t1) (depth t2)

leaves — the number of leaf (Lf) nodes:

let rec leaves = function
  | Lf -> 1
  | Br (v, t1, t2) -> leaves t1 + leaves t2

Fundamental invariants

These measures are related by two properties, provable by structural induction:

Invariant	Meaning
leaves(t) = count(t) + 1	Every tree has exactly one more leaf than branch node
count(t) ≤ 2^(depth(t)) − 1	A tree of given depth can hold at most a full binary tree’s worth of nodes

The second invariant gives a striking practical fact: a tree of depth 20 can store up to 2²⁰ − 1 ≈ one million elements. Access paths to any element are at most 20 steps long, compared with up to one million steps in a linear list.

ftree: building labelled complete trees

let rec ftree k n =
  if n = 0 then Lf
  else Br (k, ftree (2 * k) (n - 1), ftree (2 * k + 1) (n - 1))

ftree k n builds a complete binary tree of depth n where nodes are labelled according to the standard array-to-tree mapping: the root gets label k, the left child gets 2_k_, and the right child gets 2_k_ + 1. This labelling scheme is the foundation for functional arrays (Braun trees), which are covered in the following lecture.