DAA: Binary Tree and its Categories

Binary Tree and its Categories

The binary tree is a non-linear data structure in which there are 0 or utmost 2 nodes.  Each node has two children, i.e., left and right child. The top node is known as the root node. 

There are various fields where binary trees are used, such as data compression, hashing, routing data, and binary search trees.

An example is given in the below image:

The basic terminologies of a binary tree are as follows:

Node: The termination point in a tree is called a node.

Root: The first node in the tree is known as a root node.

Parent node: The node for which there exists atleast one subtree is known as the parent node of that subtree.

Child node: The node that is made from the parent node is called the child node.

Inner node: The node with atleast a single child is known as the inner node.

Depth of a tree: The total edges from a root node to the tree node are known as the depth of the tree.

Height of the tree: The total number of edges from the root to the leaf node is called the tree’s height.

What does a tree comprise of? 

Every binary tree contains three components:

1. The data of the node.
2. The left pointer to that node (To make left subtree).
3. The right pointer to that node (To make the right subtree).

C++ code of binary tree implementation:

 #include <bits/stdc++.h>
 using namespace std;
 // Create the structure of the binary tree as above components
 struct Node { // create tree structure
           int data; // The valu of node
           struct Node* left; // The left pointer to the node
           struct Node* right; // The right pointer to the node
           Node(int val) // This constructor adds a new value to the tree having the value val
           {
                    data = val; // Initialise data
                    eft = NULL; // The left child is NULL currently
                    right = NULL; // The right child is also NULL currently
           }
 };
 int main() // Main function
 {
           struct Node* root = new Node(1); // Create a root node of binary tree
           root->left = new Node(2); // For the root node the left child has value 2
           root->right = new Node(3); // For the same root node the right child has value 3
           root->left->left = new Node(4); // Adding 4 as the left child of 2
           root->left->right = new Node(5); // Adding 4 as right child of 2  
           return 0;
 } 

Types of binary trees:

The following are the binary tree types:

1. Full binary tree: The full binary tree has either 0 or two child nodes. In this type of tree, Either the parent node will have zero children or two children. The other name of a binary tree is a proper binary tree. Here the number of leaf nodes is the number of internal nodes + 1.  An example is given in the below image:

• Complete binary tree: This is the type of binary tree in which all the tree levels are filled except the lowest one, which is also filled from the left. It is almost similar to a full binary tree except the all leaf elements lean towards the left, and the last leaf may not have a right sibling. An example is given in the below image:

• Perfect binary tree: This is the type of binary tree in which every node has exactly two children, and the leaf nodes are at the same level. A perfect binary tree has (2h - 1) nodes where h is the tree’s height. An example is given in the below image:

• Balanced binary tree: The binary tree is balanced if the height of the tree is O(logN), where N is the number of nodes in the tree. Common examples of balanced trees are AVL trees and Red-black trees.

The below image is the example of a balanced binary tree:

• Degenerate Binary Tree: In this type of tree, the intern nodes have only one child, either the left or right child. Such trees can be seen as a linked list in terms of performance. The below image is an example of a degenerate binary tree:

Advantages of using a Binary Tree:

1. The search operation is faster in trees when compared to other data structures.
2. The graph traversals use a binary tree.
3. The maximum and minimum elements can be found in lower time complexities.
4. The prefix and postfix conversions are done using the binary tree method.