# 3.11. Example: Trees¶

Trees are a very useful data structure. A binary tree, as you’ll recall from CS 2110, is a node containing a value and two children that are trees. A binary tree can also be an empty tree, which we also use to represent the absence of a child node.

## 3.11.1. Representation with Tuples¶

Here is a definition for a binary tree data type:

```type 'a tree =
| Leaf
| Node of 'a * 'a tree * 'a tree
```
```type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree
```

A node carries a data item of type `'a` and has a left and right subtree. A leaf is empty. Compare this definition to the definition of a list and notice how similar their structure is:

```type 'a tree =                        type 'a mylist =
| Leaf                                | Nil
| Node of 'a * 'a tree * 'a tree      | Cons of 'a * 'a mylist
```

The only essential difference is that `Cons` carries one sublist, whereas `Node` carries two subtrees.

Here is code that constructs a small tree:

```(* the code below constructs this tree:
4
/   \
2     5
/ \   / \
1   3 6   7
*)
let t =
Node(4,
Node(2,
Node(1, Leaf, Leaf),
Node(3, Leaf, Leaf)
),
Node(5,
Node(6, Leaf, Leaf),
Node(7, Leaf, Leaf)
)
)
```
```val t : int tree =
Node (4, Node (2, Node (1, Leaf, Leaf), Node (3, Leaf, Leaf)),
Node (5, Node (6, Leaf, Leaf), Node (7, Leaf, Leaf)))
```

The size of a tree is the number of nodes in it (that is, `Node`s, not `Leaf`s). For example, the size of tree `t` above is 7. Here is a function function `size : 'a tree -> int` that returns the number of nodes in a tree:

```let rec size = function
| Leaf -> 0
| Node (_, l, r) -> 1 + size l + size r
```

## 3.11.2. Representation with Records¶

Next, let’s revise our tree type to use use a record type to represent a tree node. In OCaml we have to define two mutually recursive types, one to represent a tree node, and one to represent a (possibly empty) tree:

```type 'a tree =
| Leaf
| Node of 'a node

and 'a node = {
value: 'a;
left: 'a tree;
right: 'a tree
}
```
```type 'a tree = Leaf | Node of 'a node
and 'a node = { value : 'a; left : 'a tree; right : 'a tree; }
```

Here’s an example tree:

```(* represents
2
/ \
1   3  *)
let t =
Node {
value = 2;
left = Node {value = 1; left = Leaf; right = Leaf};
right = Node {value = 3; left = Leaf; right = Leaf}
}
```
```val t : int tree =
Node
{value = 2; left = Node {value = 1; left = Leaf; right = Leaf};
right = Node {value = 3; left = Leaf; right = Leaf}}
```

We can use pattern matching to write the usual algorithms for recursively traversing trees. For example, here is a recursive search over the tree:

```(** [mem x t] is whether [x] is a value at some node in tree [t]. *)
let rec mem x = function
| Leaf -> false
| Node {value; left; right} -> value = x || mem x left || mem x right
```
```val mem : 'a -> 'a tree -> bool = <fun>
```

The function name `mem` is short for “member”; the standard library often uses a function of this name to implement a search through a collection data structure to determine whether some element is a member of that collection.

Here’s a function that computes the preorder traversal of a tree, in which each node is visited before any of its children, by constructing a list in which the values occur in the order in which they would be visited:

```let rec preorder = function
| Leaf -> []
| Node {value; left; right} -> [value] @ preorder left @ preorder right
```
```val preorder : 'a tree -> 'a list = <fun>
```
```preorder t
```
```- : int list = [2; 1; 3]
```

Although the algorithm is beautifully clear from the code above, it takes quadratic time on unbalanced trees because of the `@` operator. That problem can be solved by introducing an extra argument `acc` to accumulate the values at each node, though at the expense of making the code less clear:

```let preorder_lin t =
let rec pre_acc acc = function
| Leaf -> acc
| Node {value; left; right} -> value :: (pre_acc (pre_acc acc right) left)
in pre_acc [] t
```
```val preorder_lin : 'a tree -> 'a list = <fun>
```

The version above uses exactly one `::` operation per `Node` in the tree, making it linear time.