Trees

You were introduced to node-based data structures in the previous chapter with linked lists. In a classic linked list, each node contains a link that connects the node to a single other node. A tree is also a node-based data structure, but within a tree each node can have links to multiple nodes.

Here is a visualization of a simple tree:

In this example, each node has links that lead to two other nodes. For the sake of simplicity, we can represent this tree visually without showing all the memory addresses:

Trees come with their own unique nomenclature:

• The uppermost node (in our example, “j”) is called the root. Yes, in our picture the root is at the top of the tree; it’s how trees are typically depicted.

• In our example, we’d say that “j” is a parent to “m” and “b”. Conversely, “m” and “b” are children of “j”. Similarly, the “m” is a parent of “q” and “z”, and “q” and “z” are children of “m”.

• As in a family tree, a node can have descendants and ancestors. A node’s descendants are all the nodes that stem from a node, while a node’s ancestors are all the nodes that it stems from. In our example, “j” is the ancestor of all the other nodes in the tree, and all the other nodes are, therefore, descendants of “j”.

• Trees are said to have levels. Each level is a row within the tree. Our example tree has three levels:

• One property of a tree is how balanced it is. A tree is balanced when its nodes’ subtrees have the same number of nodes in it.

For instance, the preceding tree is said to be perfectly balanced. If you look at each node, its two subtrees have the same number of nodes. The root node (“j”) has two subtrees, which each contain three nodes. You’ll see that the same is also true for every node in the tree. For example, the “m” node also has two subtrees where the two subtrees each contain one node.

The following tree, on the other hand, is imbalanced:

As you can see, the root’s right subtree contains more nodes than its left subtree, causing an imbalance.