Trees are a very common data structure in computer science. A tree is a
nonlinear data structure that is used to store data in a hierarchical manner.
We examine one primary tree structure in this chapter, the binary tree, along
with one implementation of the binary tree, the binary search tree. Binary
trees are often chosen over more fundamental structures, such as arrays and
linked lists, because you can search a binary tree quickly (as opposed to a
linked list) and you can quickly insert data and delete data from a binary tree
(as opposed to an array).
THE DEFINITION OF A TREE
Before we examine the structure and behavior of the binary tree, we need to
define what we mean by a tree. A tree is a set of nodes connected by edges. An
example of a tree is a company’s organization chart (see Figure 12.1).
The purpose of an organization chart is to communicate to the viewer the
structure of the organization. In Figure 12.1, each box is a node and the
lines connecting the boxes are the edges. The nodes, obviously, represent
the entities (people) that make up an organization. The edges represent the
relationship between the entities. For example, the Chief Information Officer
(CIO), reports directly to the CEO, so there is an edge between these two
nodes. The IT manager reports to the CIO so there is an edge connecting
them. The Sales VP and the Development Manager in IT do not have a direct
edge connecting them, so there is not a direct relationship between these two
Figure 12.2 displays another tree that defines a few terms we need when
discussing trees. The top node of a tree is called the root node. If a node is
connected to other nodes below it, the top node is called the parent, and
the nodes below it are called the parent’s children. A node can have zero,
one, or more nodes connected to it. Special types of trees, called binary trees,
restrict the number of children to no more than two. Binary trees have certain
computational properties that make them very efficient for many operations.
Binary trees are discussed extensively in the sections of this chapter. A node
without any child node is called a leaf.
Continuing to examine Figure 12.2, you can see that by following certain
edges, you can travel from one node to other nodes that are not
directly connected. The series of edges you follow to get from one node
to another is called a path (depicted in the figure with dashed lines). Visiting
all the nodes in a tree in some particular order is known as a tree
A tree can be broken down into levels. The root node is at Level 0, its
children at Level 1, those node’s children are at Level 2, and so on. A node at
any level is considered the root of a subtree, which consists of that root node’s
children, its children’s children, and so on. We can define the depth of a tree
as the number of layers in the tree.
Finally, each node in a tree has a value. This value is sometimes referred to
as the key value.
A binary tree is defined as a tree where each node can have no more than
two children. By limiting the number of children to 2, we can write efficient
programs for inserting data, deleting data, and searching for data in a binary
Before we discuss building a binary tree in C#, we need to add two
terms to our tree lexicon. The child nodes of a parent node are referred
to as the left node and the right node. For certain binary tree implementations,
certain data values can only be stored in left nodes and other data
values must be stored in right nodes. An example binary tree is shown in
Identifying the child nodes is important when we consider a more specific
type of binary tree—the binary search tree. A binary search tree is a binary tree
where data with lesser values are stored in left nodes and values with greater
values are stored in right nodes. This property provides for very efficient
searches, as we shall soon see.
Building a Binary Search Tree
A binary search tree is made up of nodes, so we need a Node class that is
similar to the Node class we used in the linked list implementation. Let’s look
at the code for the Node class first: