Summary

The current chapter is the longest so far in the book. However, it contains a lot of information about variants of trees. Such data structures perform very important role in many algorithms and it is good to learn more about them, as well as to know how to use them in your applications. For this reason, this chapter contains not only short theoretical introductions, but also diagrams, explanations, and code samples.

At the beginning, the concept of a tree was described. As a reminder, a tree consists of nodes, including one root. The root does not contain a parent node, while all other nodes do. Each node can have any number of child nodes. The child nodes of the same node can be named siblings, while a node without children is named a leaf.

Various variants of trees follow this structure. The first one described in the chapter is a binary tree. In this case, a node can contain at most two children. However, the rules for BSTs are even more strict. For any node in such trees, the values...