Working with binary tree data structures
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
