The Self-Taught Computer Scientist

Figure 14.1: An example of a tree data structure

---

Data Structures
148
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).
You can move from one node to another as long as they share an edge (Figure 14.3).
Every node in a tree except the root has a single parent node. A node without child nodes is called 
a leaf node, and a node with child nodes is called a branch node.
A binary tree is a tree data structure where each node can have only two child nodes (sometimes 
called a 
child or children). Every node in a binary tree (except the root) is either the left or right child 
of a parent node (Figure 14.4).
Everything else in a binary tree is the same as a general tree; the only difference is the child 
node limit.
5
Root Node
Parent Node
Child Node
Sibling Nodes
Edge
7
9
4
6
11
6
13
7
Figure 14.2: A tree with a root node, parent nodes, child 
nodes, and edges
5
Root Node
Parent Node
Child Node
Edge
7
9
4
6
11
6
13
7
Sibling Nodes
Figure 14.3: A path through a tree

---

Chapter 14 Binary Trees
149
A binary search tree is a tree data structure where each node can have only two children, and the 
tree stores its nodes in sorted order where every node’s value is greater than any value in its left subtree 
and lower than any value in its right subtree (Figure 14.5). Like hash table keys, you cannot store 
duplicate values in a binary search tree. You can get around this restriction and handle duplicate values 
by adding a count field in your tree’s node objects to track the number of occurrences of a given value.
Unlike linear data structures like arrays and linked lists, you cannot always traverse a tree without 
backtracking. You can reach any node in a tree by starting from the root node, but once you have 
moved away from the root node, you can reach only that node’s descendants. A node’s descendants 
are its children and their children and their children’s children, etc. For example, Figure 14.6 shows 
a simple tree with a root node A, leaf nodes B, D, and E, and a branch node C. The A node has two 
children (B and C), and the C node has two children (D and E). The nodes B, C, D, and E are the A 
node’s descendants.
5
Right child
Left child
7
9
4
6
11
6
13
7
Figure 14.4: In a binary tree, a parent node can have only two child nodes.
9
12
5
3
8
16
15
9
6