A binary tree is a recursive algebraic data type: a Leaf holds one value, while a Branch holds a left and right subtree. Because each branch contains smaller trees, operations follow the same shape: handle a leaf directly, then combine the results from both children. section 3.4
enum Tree[+A]: case Leaf(value: A) case Branch(left: Tree[A], right: Tree[A])
This definition makes the recursive shape explicit: values occur only at leaves, and branches connect two further trees. section 3.4
Pattern matching turns the representation into a guide for implementation. To count nodes, a leaf contributes 1; a branch contributes 1 plus the sizes of its left and right subtrees. The operation may be written as a method on every Tree[A] or as a standalone function; method syntax shortens both calls and signatures. section 3.4
Structural recursion supports several useful operations:
- maximum examines Tree[Int], returning a leaf value directly and selecting the larger result at each branch. section 3.6
- depth assigns 0 to a leaf and adds 1 to the greater subtree depth at a branch. section 3.6
- map preserves the tree's Leaf and Branch shape while transforming every leaf value. section 3.6
- firstPositive searches the left subtree first; if its result is not positive, it searches the right subtree. section 3.4
The recurring pattern behind these functions is a fold. Supply one function for leaves and another for combining two already-folded subtrees. A fold can express size, depth, map, and maximum, replacing repeated traversal logic with choices about what each case should produce. section 3.6 section 3.6
enum Tree[+A]:
def fold[B](f: A => B, g: (B,B) => B): B = this match
case Leaf(a) => f(a)
case Branch(l, r) => g(l.fold(f, g), r.fold(f, g))
Fold exposes the two decisions in every tree traversal: transform a leaf, then combine the results from a branch's subtrees. section 3.6
Preserving structure with map
Mapping a tree does not flatten or rearrange it. Each Leaf becomes a new Leaf containing the transformed value, and each Branch becomes a Branch of recursively mapped children. This mirrors list map: constructors are rebuilt in the corresponding shape. section 3.6 section 3.6
