Introduction

Trees are a common data structure used in a variety of data analysis techniques. A tree is a hierarchical connection of nodes under one all-encompassing mighty root node. Every node can have zero or more children, but each child node associates with only one parent. Also, the root is the only special case that has no parent node. All nodes without children are also referred to as leaf nodes.

In Haskell, we can very gracefully represent a tree since the recursive nature of the data structure makes use of the recursive nature of functional programming. This section will cover creating our own trees as well as using existing implementations from libraries.

We will implement heaps and Huffman trees, which are some of the most notable examples of trees in data analysis. In other chapters throughout the book, we also run into HTML/XML traversal, hierarchical clustering, and decision trees, which all depend heavily on the tree data structure.