Introduction To Binary Trees

Computer science and its concepts are all about designing hierarchical data structures in a well-defined and efficient manner. As a computer programmer, this is the area where your expertise will be tested the most.

This is what the binary tree structure is all about. When observed as a hierarchical structure you will find that the tree consists of nodes that are linked together.

After implementing the program of a Binary Tree you will observe that the data can be presented in an efficient and effective manner.

Though you may have heard about binary trees multiple times, today we will be giving a detailing of this topic in this blog.

What is a binary tree?

The structure of a Binary Tree can be defined as a hierarchical data structure where data is stored in nodes of the tree. The tree starts with a root or the ancestral node which expands into one or two children nodes.

The key feature of a binary tree is that you can trace back every single child node to their parent and ultimately to the last ancestral node of the tree.

This node is in other terms known as the root of the tree. This is the starting node that branches out into different formats which we will discuss further in this blog.

But, let us first discuss the properties of a binary tree.

Properties of a binary tree

Here are some of the key properties of a binary tree:

=> The root node of a Binary Tree is considered to be at a 0 level. This node is allowed to have two children nodes at maximum.

=> Every node at the end of a binary tree with no children is referred to as the leaf node. You can determine the number of leaf nodes in a Binary Tree by taking into account the number of parent nodes. You will observe that the leaf nodes count will be greater by one.

=> Starting from any given lead node you can always trace back to the root or ancestral node of the binary tree by taking into account each parent node along the way.

=> Binary trees can be constructed in six different structures.

Now that we are on the subject let us consider the four different types of binary trees.

Types of binary trees

There are six basic types of binary trees that are available:

=> Full Binary Tree

Within a full binary tree, every single parent node has either two or zero children nodes.

=> Perfect Binary Tree

A perfect binary tree is one that has all the leaf nodes at the exact same level. Also, every parent node in a perfect binary tree has two child nodes.

=> Complete Binary Tree

Within the structure of a complete binary tree, you will observe that every single node has been completely filled out. This means that every single parent node has two children nodes.

The only point that differentiates the complete binary tree from a perfect binary tree is that all the leaf nodes of this structure are angled to the left.

=> Pathological Tree

Within the structure of a pathological tree, every single node consists of only one child node either a right or a left child.

=> Skewed Binary Tree

This is a slightly different version of the pathological tree. Within this structure, we have every parent extending to a single child node either left or right. Also, an interesting structural characteristic of the skewed tree is that the structure is either leaning towards the right or the left.

=> Balanced Binary Tree

In a balanced binary tree, each sub-tree is at the same level. A subtree in a binary tree is referred to the different levels of parent nodes which extend further into children nodes and so forth.

The root of the binary tree is not considered to be a subtree level. But, every single level after that definitely falls under the category of a subtree.

Now that we have covered the important concepts of a Binary Tree, Let us head to the second part of the blog and discuss a few structural properties of the top view of a binary tree and the right view of a binary tree.

Top view of a binary tree

Understanding the top view of a Binary Tree involves taking into consideration what its structure looks like when viewed from the top angle.

Here is a problem statement related to this concept which you can solve using the approach we have discussed below:

Q. You have been provided the structure of a binary tree. Print out the output for its top view. You can print the output nodes in any desired order.

Approach:

For printing the output of this problem statement you do not require to employ the queue algorithm. All you have to do is use two different variables to pan out the whole structure of the list.

From any given node you are required to take into consideration the vertical length of the tree till the root node, simultaneously you will also have to consider the depth of the tree from the same node till you reach the root node of the tree.

Next up, we will look at a problem statement related to printing the right view of a binary tree.

Right view of a binary tree

Problem statement:

You have been provided a key in a given binary tree structure. You will have to print the right nodes while referring to the key.

Approach

The approach for this problem statement would be to employ the level order traversal concept. Within this concept, the given key point is taken into consideration and you will have to figure out the nodes that are present to the right of the key.

The problem statement will be considered to be solved once you confirm that the last node of the Binary Tree is at the same level as its key node.

Winding Up

The top view of a Binary Tree and the right view of a Binary Tree is quite a lengthy field of study on its own, and concepts such as the binary tree make it seem more difficult to cover than usual.

If we take into account the details that we have discussed so far, we conclude that the concept of a binary tree is easier to understand and apply in programming.

Akshay is a tech expert and dealing with different programming languages i.e Java, Python, Data Science, & Sql.