Fundamentals of Binary Trees

Binary Tree: data structure in which each node can have a left child and a right child. They cannot have more than two children.

Common uses of binary trees are binary search trees, binary heaps, and Huffman coding.

Implementation:

data Bintree = Empty | Node Int Bintree Bintree
    deriving (Show)

If we wanted to compute the height of the tree:

height :: Bintree -> Int
height Empty = 0
height (Node _ leftChild rightChild) = 1 + max (height leftChild) (height rightChild)

Binary Tree of generic data type:

data Bintree a = Empty | Node a (Bintree a) (Bintree a)
    deriving (Show)

-- Usage with Int
t1 :: Bintree Int
t1 = Node 3 (Node 1 Empty Empty) (Node 2 Empty Empty)