PYTHON

Mihalis Tsoukalos explains how to construct and use binary trees for faster searches and easier relationships (of the data sort, mind).

OUR EXPERT

Mihalis Tsoukalos is a systems engineer and a technical writer. You can reach him at www. mtsoukalos.eu and @mactsouk.

The main benefit of using a binary tree or a tree in general is that you can quickly find out if an element is present or not, compared to performing a linear search. Trees are also good at modelling relationships and hierarchical data. Let’s begin by discussing the basics of binary trees before we start implementing binary trees in Python.

Get to grips with the basic concepts

Strictly speaking, a tree is a directed acyclic graph that satisfies the following three principles. First, it has a root node that’s the entry point to the tree. Second, every vertex, except the root, has only one entry point. Third, a path connects the root with each vertex. A directed graph features edges that have a direction associated with them. A directed acyclic graph is a directed graph that lacks cycles.

As already stated, the root of a tree is the first node of the tree. Each node can be connected to one or more nodes depending on the tree type. If each node leads to one and only one node, then the tree becomes a linked list. A leaf node is a node without any children. Leaves are also called external nodes, whereas a node with at least one child is called an internal node.

A binary tree is a specific type of tree where underneath each node there exist at most two more nodes. ‘At most’ means that it can be connected to one, two or no other node. The depth of a tree, which is also called the height of a tree, is defined as the longest path from the root node to a leaf, whereas the depth of a node is the number of edges from the node to the root node of the tree.

If you create two binary trees based on the same set of elements added in a different order, then you’re going to produce two completely different trees. The simplest way to do that’s by starting from a different root node.So, in general, we don’t know in advance the final shape of our trees.

The screenshot (above) shows two sample binary trees. The tree on top is a “good” binary tree because it’s balanced (the term is going to be explained shortly). The tree on the bottom of the image is not a very “good” binary tree.

This figure shows two binary trees: a balanced tree on top and an unbalanced one. Generally speaking, balanced trees are preferred.