We discuss two common variants of trees and show some typical functions of each variant.

A *binary tree* is either of the
following: a singleton value called *empty*
(also *null* or *leaf*) or a pair, called a
*branch*, consisting of two
binary trees called the *left* and the *right child*.
Most often, a branch is a triple rather than a pair
which in addition to the children
also stores a value of some generic set. This value
is called the *root* or *decoration*
of the tree.

A (decorated) binary tree is declared in Curry as:

data BinTree a = Leaf | Branch a (BinTree a) (BinTree a)

where BinTree is a *type constructor*
and $a$ is its parameter and stands for the type of the
decorations.
A popular variant of binary trees is called a
*binary search tree*.
The set of decorations is totally ordered and the decoration
of a non-empty binary search tree is greater than all the decorations
in the left child and smaller than all the decorations
in the right child.
This condition prevents repeated decorations in a binary search tree.
The following function inserts a value in a binary search tree
in such a way that the result is again a binary search tree
[Browse Program][Download Program]:

insert x Leaf = Branch x Leaf Leaf

insert x (Branch d l r)

| x < d = Branch d (insert x l) r

| x > d = Branch d l (insert x r)

| otherwise = Branch d l r

An in-order traversal of any binary search tree produces the sorted list of the decorations of the tree.

Sort a list without repeated values by constructing a binary search tree from the list and then traversing the tree [Browse Answer][Download Answer].

An *ordered tree* is a pair
in which the first component is an element of a set,
called the set of decorations, and the second component
is a sequence of ordered trees.

An ordered tree is declared in Curry as:

data Tree a = Tree a [Tree a]

where $a$ is a parameter that stands for the type of the
decorations and the identifier “*Tree*” is overloaded to
denote both a type constructor (1st and 3rd occurrences)
and a data constructor (2nd occurrence).

A *trie* is a tree that stores a mapping from keys,
typically strings, to values and is characterized by sharing
key prefixes. We present a simple variant where only keys
are stored. This variant is useful to efficiently
represent a dictionary and tell whether a string is
in the dictionary.

We declare the type of a trie as follows:

type Trie = [Tree Char]

The following function inserts a string in a trie sharing whatever prefix of the string might already be present in the trie. The distinguished symbol that terminates a string is a period. [Browse Program][Download Program]

insert :: String -> Trie -> Trie

insert [] t = (Tree '.' [] : t)

insert (w:ws) [] = [Tree w (insert ws [])]

insert (w:ws) (Tree c cs : ts)

| ord w < ord c = insert (w:ws) [] ++ (Tree c cs : ts)

| ord w > ord c = Tree c cs : insert (w:ws) ts

| otherwise = Tree c (insert ws cs) : ts

Code functions to build a trie from a list of words and to print all the words in the trie [Browse Answer][Download Answer].

Code a function that takes a word and a trie and tells whether or not the word is in the trie [Browse Answer][Download Answer].