sml-examples/binary-tree.sml

(*

A binary tree of elements of generic type 'a is EITHER:

(1) a Leaf carrying a value of type 'a OR
(2) a Node, carrying a tuple of values of the types:

  (left) binary tree, containing values of type 'a,
  (node value) a value of type 'a,
  (right) binary tree containing values of type 'a

*)

datatype 'a btree = Leaf of 'a
                  | Node of 'a btree * 'a * 'a btree; (* three-arg constructor *)

(* Here is a binary tree *)
val myTree = Node (Leaf 9, 8, Node (Leaf 3, 5, Leaf 7));

(* This function counts the sum of all the elements in a tree *)
fun count (Leaf n) = n
  | count (Node (leftTree, n, rightTree)) = count leftTree + n + count rightTree;

val myTreeCount = count myTree;