Binary Trees

This chapter is from the book

Data Structures & Algorithms in Python

Learn More Buy

This chapter is from the book

This chapter is from the book 

Data Structures & Algorithms in Python

Learn More Buy

Tree Terminology

Many terms are used to describe particular aspects of trees. You need to know them so that this discussion is comprehensible. Fortunately, most of these terms are related to real-world trees or to family relationships, so they’re not hard to remember. Figure 8-2 shows many of these terms applied to a binary tree.

FIGURE 8-2 Tree terms

Root

The node at the top of the tree is called the root. There is only one root in a tree, labeled A in the figure.

Path

Think of someone walking from node to node along the edges that connect them. The resulting sequence of nodes is called a path. For a collection of nodes and edges to be defined as a tree, there must be one (and only one!) path from the root to any other node. Figure 8-3 shows a nontree. You can see that it violates this rule because there are multiple paths from A to nodes E and F. This is an example of a graph that is not a tree.

FIGURE 8-3 A nontree

Parent

Any node (except the root) has exactly one edge connecting it to a node above it. The node above it is called the parent of the node. The root node must not have a parent.

Child

Any node may have one or more edges connecting it to nodes below. These nodes below a given node are called its children, or sometimes, branches.

Sibling

Any node other than the root node may have sibling nodes. These nodes have a common parent node.

Leaf

A node that has no children is called a leaf node or simply a leaf. There can be only one root in a tree, but there can be many leaves. In contrast, a node that has children is an internal node.

Subtree

Any node (other than the root) may be considered to be the root of a subtree, which also includes its children, and its children’s children, and so on. If you think in terms of families, a node’s subtree contains all its descendants.

Visiting

A node is visited when program control arrives at the node, usually for the purpose of carrying out some operation on the node, such as checking the value of one of its data fields or displaying it. Merely passing over a node on the path from one node to another is not considered to be visiting the node.

Traversing

To traverse a tree means to visit all the nodes in some specified order. For example, you might visit all the nodes in order of ascending key value. There are other ways to traverse a tree, as we’ll describe later.

Levels

The level of a particular node refers to how many generations the node is from the root. If you assume the root is Level 0, then its children are at Level 1, its grandchildren are at Level 2, and so on. This is also sometimes called the depth of a node.

Keys

You’ve seen that one data field in an object is usually designated as a key value, or simply a key. This value is used to search for the item or perform other operations on it. In tree diagrams, when a circle represents a node holding a data item, the key value of the item is typically shown in the circle.

Binary Trees

If every node in a tree has at most two children, the tree is called a binary tree. In this chapter we focus on binary trees because they are the simplest and the most common.

The two children of each node in a binary tree are called the left child and the right child, corresponding to their positions when you draw a picture of a tree, as shown in Figure 8-2. A node in a binary tree doesn’t necessarily have the maximum of two children; it may have only a left child or only a right child, or it can have no children at all (in which case it’s a leaf).

Binary Search Trees

The kind of binary tree we discuss at the beginning of this chapter is technically called a binary search tree. The keys of the nodes have a particular ordering in search trees. Figure 8-4 shows a binary search tree.

FIGURE 8-4 A binary search tree