13 Binary Trees

Let's take a look at another example of variants, binary trees.

In a binary tree, each node can have two children:

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

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

We can make a tree!

let t = Node (2,
	Node (1, Leaf, Leaf),
	Node (3, Leaf, Leaf)
)

val t : int tree = Node (2, Node (1, Leaf, Leaf), Node (3, Leaf, Leaf))

This list is:

mermaid
2 --> 1
2 --> 3

As you can see, binary trees are super easy to implement in OCaml!

let rec sum = function
	| Leaf -> 0
	| Node (v, l, r) -> v + sum l + sum r

val sum : int tree -> int = <fun>

sum t

- : int = 6