Binary tree – What is it, definition and concept | 2022

A binary tree can be defined as a data structure used in computer science. This structure begins with a root that then extends into two branches until they finally end in a leaf.

In other words, a binary tree could be said to start with a node that functions as a root. Then, from that root two new nodes or branches that are known as children originate.

Each root can only have two children or branches. For that reason, it is called a binary tree. One branch is presented to the right side and the other to the left side.

Indeed, a binary tree is a data structure that relates information in a non-linear hierarchical manner. For this reason, it is precisely called a tree because of the way the information is presented. The information is structured in a branched way as if it were a tree. Additionally, it is binary because only two branches are given off.

Keep learning economics, finance and investment

Learn from scratch to improve your finances and investments, or specialize in the most in-demand areas of financial work: investing, stocks, savings, asset management, banking, business analysis, and accounting. All courses in a single subscription.

Now you can watch the first episode of each course for free:

How is a binary tree structured?

To begin with, a binary tree represents a finite set of elements and the whole set is divided into three separate parts or subsets. Each element that makes up the binary tree is called a tree node, and when a node does not have a child or subtree, it is known as a leaf.

See also  Simple majority - What it is, definition and concept

It is structured as follows:

  • Root: The root is the first subset and contains only one element.
  • Left Subtree: It represents a second subset and is also a binary tree. It is recognized as the left subtree of the original tree.
  • Right Subtree: The third subset is also a binary tree and is known as the right subtree of the original tree.
Binary Tree 1
binary tree
How is it structured?

Classification of the nodes

The nodes that form a binary tree can be classified as follows:

  • Parent node: The parent node is the node that gives rise to other nodes called children. But, it is a node that has no parent or does not originate from another.
  • Branch node: It is a node that has the characteristic that it has children and also has a parent. That is, it originates from another node and other nodes derive from it.
  • Leaf node: This is a node that has a parent, but no children. In this case the node is derived from another node. However, this node no longer originates another.

Ways to traverse a binary tree

Now, the tour is the process of order or sequence that must be used to visit the nodes that compose it. This allows you to follow a specific order and determine how the information is structured and organized.

A binary tree can be traversed by following its breadth or following its depth.

1. Amplitude travel

Of course, breadth traversal is done when tree traversal is done starting at the top level. To later go down to the lower levels. For example, if we had the following graph of a tree, the path would be as follows:

12, 8, 17, 5, 9 and 15.

Binary Tree 2
Amplitude travel

2. Tour in depth

On the other hand, depth traversal is performed when traversing along subtrees. To do this, a different sequence can be followed. You can follow a preorder, central order or postorder process.

  • Preorder: In this case the traversal starts with the root, then the left subtree is traversed, and the traversal ends with the right subtree. Each subset is parsed in preorder.
  • Center Order: For its part, the traversal in central order starts traversing the left subtree, then goes to the root and the traversal ends with the right subtree.
  • Postorder: For postorder traversal, traversal should start at the left subtree, then move to the right subtree, and traversal ends at the root. Each tour is done in postorder.
Binary Tree 3
Preorder depth walkthrough
Binary Tree 4
Central order depth traversal
Binary Tree 5
Postorder depth traversal

In conclusion, it can be stated that a binary tree is a structure that is widely used in computer science and can also be used in mathematics. The fundamental part for its structure is the node. Relationships are established within nodes. A binary tree can only have two branches and always ends in a leaf.

Leave a Comment