The Basics of Tree Structures Used in Algorithms

By John Paul Mueller, Luca Massaron

A tree structure looks much like the physical object in the natural world. Using trees helps you organize data quickly and find it in a shorter time than using other data-storage techniques. You commonly find trees used for search and sort routines, but they have many other purposes as well.

Building a tree works much like building a tree in the physical world. Each item you add to the tree is a node. Nodes connect to each other using links. The combination of nodes and links forms a structure that looks much like a tree, as shown here.

algorithms-trees
A tree in Python looks much like the physical alternative.

Note that the tree has just one root node— just as with a physical tree. The root node provides the starting point for the various kinds of processing you perform. Connected to the root node are either branches or leaves. A leaf node is always an ending point for the tree. Branch nodes support either other branches or leaves. The type of tree shown is a binary tree because each node has, at most, two connections.

In looking at the tree, Branch B is the child of the Root node. That’s because the Root node appears first in the list. Leaf E and Leaf F are both children of Branch B, making Branch B the parent of Leaf E and Leaf F. The relationship between nodes is important because discussions about trees often consider the child/parent relationship between nodes. Without these terms, discussions of trees could become quite confusing.