Recursive data: binary trees

A recursive type

A data type may refer to itself. That single feature builds lists, trees, and syntax trees, which is why algebraic data types carry most of the weight in Haskell programs:

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Show, Eq)

A tree is a leaf or a node with a left subtree, a value, and a right subtree. The type parameter a means the tree can hold any element type, and the declaration does not mention ordering at all.

Insert in order

Ordering is a property of the algorithm, not of the type. An insert that keeps smaller values left and larger values right turns the tree into a search tree:

insert :: Ord a => a -> Tree a -> Tree a insert x Leaf = Node Leaf x Leaf insert x (Node l y r) | x < y = Node (insert x l) y r | x > y = Node l y (insert x r) | otherwise = Node l y r -- already present

The last guard makes the insert idempotent. Dropping it turns a set into a multiset, which is a design decision worth writing down.

Walk the tree

An in-order traversal visits the left subtree, then the value, then the right subtree. On a search tree that produces a sorted list:

toList :: Tree a -> [a] toList Leaf = [] toList (Node l x r) = toList l ++ [x] ++ toList r

This version is correct and quadratic, because ++ copies the left result at every node. A difference list or an accumulator fixes it, and lesson 42 revisits the same problem with folds.

Size and depth

Two measurements show the same recursion with different arithmetic. Both need the max of two branches, which is where a tree differs from a list:

size :: Tree a -> Int size Leaf = 0 size (Node l _ r) = 1 + size l + size r depth :: Tree a -> Int depth Leaf = 0 depth (Node l _ r) = 1 + max (depth l) (depth r)

Building a tree from a sorted list makes a linked list of depth n, which is the classic degenerate case. Real implementations rebalance, and the shape of the type does not stop them.

Next: Functor

Article author: Arthur Isaev