Chapter 4. Binary Trees
A tree is a data structure that simulates a hierarchical tree structure with a root node and children nodes. A child node can have children nodes of its own, thus realizing the hierarchy. Just like a list, a tree is defined recursively.
A binary tree is a tree in which each node has zero, one, or at most two child nodes. See http://opendatastructures.org/ods-java/6_Binary_Trees.html for an excellent refresher on binary trees.
In this chapter, we will look at the functional implementation of binary trees. As in the previous chapter, we will not perform any in-place mutations. Any update operation will preserve the earlier version, thereby making it a persistent binary tree.
We will implement many common binary tree algorithms. After covering binary trees, we will look at Binary Search Trees.
