Data structures are classified into linear and non-linear data structures. A tree is a non-linear data structure. Data is stored hierarchically in a non-linear data structure. So the tree is a way of organizing data hierarchically. A tree grows from top to bottom. In a tree, there are different kinds of nodes that are linked with each other. A tree consists of the following elements:

Node: It is an element of a tree.
Root: It is the starting node of a tree. It is the top most element that has no parent element.
Parent Node: It is the node that has branches from top to bottom. It is the immediate predecessor of any node.
Child Node: It is the node that has a node from bottom to top. It is the instantaneous successor of any node.
Level: Each step in a tree is level.
Leaf Node: It is the node having no child.
Non-Leaf Node: It is the node having at least one child.
Edge: It is the link between two nodes.
Sibling: It is the child node with the same parents.
Internal Nodes: These are the nodes that have child nodes.
Degree: It is the largest number of child nodes.
Path: It is a sequence of nodes along with the boundaries of a tree.

In a binary tree, every node in a tree should have a maximum of two children. It means that a tree can constitute either 0, 1, or 2 nodes. Let’s consider a tree shown below. In this figure, node ‘a’ has two children(b and f). Similarly, node b has also two children (d and e) and the same for node f. And node ‘f ’ has also two children (g and h) Each node has a maximum of two children. A binary tree usually consists of three nodes:

Root Node
Internal Node
Leaf Node

Types of Binary Tree

It has been classified into the following different categories:

Full Binary Tree.
Perfect Binary Tree.
Almost Complete Binary Tree.
Complete Binary Tree.
Left Skewed Binary Tree.
Right Skewed Binary Tree
Balanced Binary Tree

1. Full Binary Tree

It is also known as a strictly or proper binary tree. In this, every single node has two or zero children excluding the leaf nodes. Let us consider the following example, in which we have parent nodes (a,b,c,d) and leaf nodes(e,f,g,h,k). Each of the parent nodes has exactly two or zero children but leaf nodes have no children.

Properties of Full Binary Tree

It has the following properties:

It has the following maximum range of nodes :

And x= height of the full binary tree

2. Its minimum range of nodes is:

3. Its maximum height for 'n' nodes is:

4. Its minimum height for 'n' nodes is:

5. The range of leaf nodes for 'n' internal nodes is :

2. Perfect Binary Tree

In this type, all the internal nodes must have two children and the entire leaf nodes are at a similar level. This can be a full and complete binary tree as well.

To understand, let us consider an example shown below. This binary tree consists of three levels: internal nodes contain two child each and leaf nodes are also at an equal level.

Properties of Perfect Binary Tree

It has the following properties:

The leaf nodes for 'x' height in it are:

2. The range of internal nodes in it is:

And x= height of the tree.

3. The maximum range of nodes in it is:

4. The minimum range of nodes in it is:

3. Almost Complete Binary Tree

It is also named an “incomplete binary tree”. In this sort of binary tree, every single node must have two children in all levels apart from the last level but the first left child should be filled and then the right one.

Let us consider an example below. In this , there are a total five levels(0,1,2,3,4). In level 1, there are a total of 2 nodes in which each of the nodes has two children. Similarly, level 2 has 4 and level 3 has 8 nodes with their corresponding two children. Then we have two leaf nodes x and y at the end which are filled from left to right.

4. Complete Binary Tree

This is also called the “perfect binary tree”. In this, all levels are completely filled. And every node in each level must have two children and each level must comprising of 2N nodes. Where ‘N’ is the level number. And the last level has nodes as left as possible.

Let’s consider the following example. There are total four levels (0,1,2,3). Each level has the range of nodes in the following sequence:

Properties of Complete Binary Tree

It has the following properties:

The maximum range of nodes in it are:

And x= Tree height.

2. The minimum range of nodes in it are:

3. Its maximum height for 'n' number of nodes is:

4. Its minimum height for 'n' number of nodes is:

5. Left Skewed Binary Tree

It consists of nodes consisting of only left children. It has only left subtree or only left children. It is the left side-dominated tree. All the right side children remain null.

Let us consider an example as shown below. In this, the root node is ‘a’ and the leaf node is ‘d’. While internal nodes are ‘b’ and ‘d’.

6. Right Skewed Binary Tree

In this type of binary tree, there exist nodes consisting of only the right children. It is vice versa of the left-skewed binary tree. It is a right-side-dominated tree. It contains no left child.

Following is the example of a right-skewed binary tree. ‘a’ and ‘b’ are root and leaf nodes while ‘b’ and ‘c’ are internal nodes.

7. Balanced Binary Tree

In this, the height of the left subtree and right subtree of every single node might vary by one.

Let's consider the following example. As it can be seen, the height of the left subtree is three. And the height of the right subtree is two. So their height difference will be 1. Hence it is a balanced binary tree.

Binary Tree Representation

A binary tree can be represented by two methods.

Using Array Method
Using the Linked List Method

1. Array Method

In this method, a binary tree is represented using a single-dimensional array. So for this purpose, the root node will be considered at zero index position. Based on the position of the parent, the left and right child will be calculated. So, the left child will be placed at '2n+1' and the right child will place at '2n+2'. Here n is the position of parent.

Example

Let us consider the following example of the array method in which a binary tree has been taken as shown below which will be stored in a one-dimensional array. In this tree, ‘a’ is the root node. Node ’b’ has two children ‘d’ and ‘e’. While nodes ‘d’ and ‘e’ has one left node each.

In this tree, ‘a’ is the root node so it will be placed at zero index in an array.

For the index position of left child ‘b’ :

For the index location of the right child ‘c’:

For the index location of the left child of ‘d’:

For the index location of the right child of ‘e’:

For the index location of the left child of ‘f’:

For the index location of the left child of ‘g’:

2. Linked List Method

In this, a double-linked list will be used to represent every single node of the binary tree. In a doubly-linked list, there will be three fields i.e. address of the left child, root and address of right child fields.

Example

Let us consider an example in which a binary tree has been taken with two children on each node. ’a’ is the root node in this tree. Every node has a left and right pointer. The left pointer will point towards the left child of the node and the right pointer will point towards the right node. The left and child addresses for leaf nodes will be assigned as ‘Null Address’.

Binary Tree Traversals

A binary tree consists of different nodes. So there are three methods to traverse a tree:

Inorder Traversal
Preorder Traversal
Postorder Traversal

1. Inorder Traversal

Inorder traversal means that the left child comes first in the order then the root node and right child will come. It has the following traversal order:

Left Child >> Root Node >> Right Child

To understand this, let us consider the following tree:

In the above tree, a root node is ‘a’ while left and right nodes are ‘b’ and ‘c’.Its inorder traversal will be:

2. Preorder Traversal

Preorder traversal means that the root node comes first in the order then left child and right child will come. It has the following traversal order:

Root Node >> Left Child >> Right Child

To understand its concept, we will consider the above binary tree. Its preorder traversal will be:

3. Postorder Traversal

Postorder traversal means that the left child comes first in the order then the right child and root node will come. It has the following traversal order:

Left Child >> Right Child >> Root Node

To understand its concept, we will consider the previous binary tree. Its postorder traversal will be:

Example

To understand the concept of binary tree traversals, let us consider the following binary tree. It has an ‘1’ root node.

For inorder traversal , we have:

For preorder traversal, we have:

For postorder traversal, we have:

Properties of Binary Tree

It has the following properties:

The maximum range of nodes in it is:

And x= Tree height

2. The minimum range of nodes in it is:

3. Its maximum height for 'n' number of nodes is:

4. Its maximum height tree for 'n' number of nodes is:

Application of Binary Tree

It has the following applications:

It is used to find duplicate nodes.
It is also used in sorting and in the traversal.
Its practical application is in an organization where binary trees are used to organize data in a sequence.
It is also used in machine learning, database tables, encryption and routing.