The Self-Taught Computer Scientist

14Binary Trees

The most powerful people are the ones who never stop learning.

Rejoice Denhere

So far, all the data structures you've learned about have been linear. In the following chapters, you will learn about a few essential nonlinear data structures and abstract data types. The first one we will discuss is a tree, a nonlinear abstract data type made up of nodes connected in a hierarchical structure (Figure 14.1). Common tree operations include inserting, searching, and deleting.

Figure 14.1 An example of a tree data structure

There are several types of tree data structures: general trees, AVL trees, red-black trees, binary trees, binary search trees, and more. In this chapter, you will learn about general trees, binary search trees, and binary trees, with an emphasis on binary trees. Although covering every type of tree is outside of the scope of this book, I encourage you to learn more about other types of trees on your own.

A general tree is a data structure that starts with a node at the top. The node at the top of a tree is called the root node. Each node connected underneath a node in a tree is its child node. A node with one or more child nodes is called a parent node. Sibling nodes share the same parent. The connection between two nodes in a tree is called an edge (Figure 14.2).

Figure 14.2 A tree with a root node, parent nodes, child nodes, and edges