A simple recursive data declaration is enough to define a tree.

1 |
data Tree a = Empty | Node a (Tree a) (Tree a) |

This simply states that a Tree of ‘a’s is either Empty or (‘|’) it has a Node that has an ‘a’ and two other trees, a left subtree and a right subtree.

The code to add an item to a tree is equally simple and recursive.

1 2 3 4 5 |
add :: (Ord a) => Tree a -> a -> Tree a add Empty x = Node x Empty Empty add (Node n left right) x | x <= n = Node n (add left x) right | otherwise = Node n left (add right x) |

The function signature

1 |
add :: (Ord a) => Tree a -> a -> Tree a |

states that ‘add’ takes a Tree of ‘a’, a value to add and returns a Tree of ‘a’. The only restriction on ‘a’ being that it must be of type ‘Ord’ meaning two ‘a’s can be compared to determine that larger one.

Line 2 of the add function shows that adding an item to an Empty tree is just a matter of creating a Node with the item along with two Empty subtrees.

When adding an item in the more general case then if the item is less than the entry in the current Node then the item is added, recursively, to the left subtree otherwise it is recursively added to the right subtree.

Done!