Mastering JavaScript Functional Programming - Second Edition

Binary trees in Haskell

Consider a binary tree. Such a tree may either be empty or consist of a node (the tree root) with two sons: a left binary tree and a right one. A node that has no sons is called a leaf.

In Chapter 9, Designing Functions – Recursion, we worked with more general tree structures, such as a filesystem or the browser DOM itself, which allow a node to have any number of sons. In the case of the trees we are working with in this section, each node always has two sons, although each of them may be empty. The difference may seem minor, but allowing for empty subtrees is what lets you define that all nodes are binary.

Let's make a digression with the Haskell language. In it, we might write something like the following; a would ...