What Is Binary Tree

Table of contents

The Binary tree is the most important non linear type of data structure in which there can be a maximum of two child nodes.

The binary name itself means only 2, therefore, each node can have either 0, 1, or 2 children.

In a binary tree, the maximum degree of any node is at most two. That means, there may be a zero-degree node (empty tree) or a one-degree node and two-degree node.

Also Read: What is Tree

Binary Tree Example

The above tree is a binary tree because each node contains the utmost two children. It has either 0 or 2 child nodes.

Logical Representation of Binary Tree

Logical representation binary tree — binary tree logical

In the above tree, node A contains two pointers, i.e., left and a right pointer pointing to the left and right node respectively.

Node B contains both the nodes (left and right node); therefore, it has two pointers (left and right).

The nodes C, D, and E are the leaf nodes, so all these nodes contain NULL pointers on both left and right parts.

Properties of Binary Tree

At each level of i, the maximum number of nodes is 2ⁱ.
The height of the tree is defined as the longest path from the root node to the leaf node.
In general, the maximum number of nodes possible at height h is (2⁰ + 2¹ + 2²+….2^h) = 2^h+1 -1.
The minimum number of nodes possible at height h is equal to h+1.
If the number of nodes is minimum, then the height of the tree would be maximum.
Conversely, if the number of nodes is maximum, then the height of the tree would be minimum.

Types of Binary Trees

There are five types of Binary trees:

Strictly Binary tree
Complete Binary tree
Perfect Binary tree
Degenerate Binary tree
Balanced Binary tree

1. Strictly Binary tree

A strictly binary tree can be defined as that kind of binary tree in which each node must contain exactly 2 children nodes except the leaf nodes.

Or, if every non-terminal node in a binary tree consists of a non-empty left subtree and right subtree, then it is called a strictly binary tree.

The Full binary tree is also known as a strict binary tree.

Example of the Full Binary tree.

full or strict binary tree — Strict Binary Tree

In the above tree, we can observe that each node is either containing zero or two children; therefore, it is a Full Binary tree.

2. Complete Binary Tree

The complete binary tree is a tree in which all the nodes are completely filled except the last level.

In the last level, or the lowest level of this binary tree, every node should possibly reside on the left side.

How to create a complete binary tree.

complete binary tree example — complete binary tree

The above tree is a complete binary tree because all the nodes are completely filled, and all the nodes in the last level are added at the left first.

In a complete binary tree, there is exactly:

1 node at level 0,
2 nodes at level 1,
4 nodes at level 2,
And so on.

3. Perfect Binary Tree

A binary tree can be called a perfect binary tree if all the internal nodes have 2 children nodes, and all the leaf nodes are at the same level.

Example of a perfect binary tree.

Perfect type of binary tree — Perfect Binary Tree

4. Degenerate Binary Tree

The degenerate binary tree is a tree in which all the internal nodes have only one child.

The degenerate binary tree is of two types.

Right Skewed
Left Skewed

Right Degenerate binary tree.

The above tree is a degenerate binary tree because all the nodes have only one child. It is also known as a right-skewed tree as all the nodes have a right child only.

Left Degenerate binary tree.

The above tree is also a degenerate binary tree because all the nodes have only one child. It is also known as a left-skewed tree as all the nodes have a left child only.

5. Balanced Binary Tree

The balanced binary tree is a tree in which both the left and right trees differ by at most 1.

For example, AVL and Red-Black trees are balanced binary trees.

Binary Tree Implementation

Arrays
Linked Lists

Binary Tree Using Arrays

…

Binary Tree Using Linked Lists

A Binary tree can be implemented with the help of linked lists as pointers. The first node in the tree is represented by the root pointer.

Each node in the tree consists of three parts,

Data Part
Left Pointer
Right Pointer

To create a binary tree, we first need to create the node. We will create the node of user-defined as shown below:

struct node  
{  
   int data; 
   struct node *left, *right;  
};

In the above structure, data is the value, the left pointer contains the address of the left node, and the right pointer contains the address of the right node.

Binary Tree C++ Program

 // C++ program to insert element in Binary Tree

#include <iostream>
#include <queue>
using namespace std;

/* A binary tree node has data, pointer to left child
and a pointer to right child */

struct Node {
	int data;
	Node* left;
	Node* right;
};

/* Function to create a new node */

Node* CreateNode(int data)
{
	Node* newNode = new Node();
	if (!newNode) {
		cout << "Memory error\n";
		return NULL;
	}
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}

/* Function to insert element in binary tree */

Node* InsertNode(Node* root, int data)
{
	// If the tree is empty, assign new node address to root
	if (root == NULL) {
		root = CreateNode(data);
		return root;
	}

	// Else, do level order traversal until we find an empty
	// place, i.e. either left child or right child of some
	// node is pointing to NULL.
	queue<Node*> q;
	q.push(root);

	while (!q.empty()) {
		Node* temp = q.front();
		q.pop();

		if (temp->left != NULL)
			q.push(temp->left);
		else {
			temp->left = CreateNode(data);
			return root;
		}

		if (temp->right != NULL)
			q.push(temp->right);
		else {
			temp->right = CreateNode(data);
			return root;
		}
	}
}

/* Inorder traversal of a binary tree */

void inorder(Node* temp)
{
	if (temp == NULL)
		return;

	inorder(temp->left);
	cout << temp->data << ' ';
	inorder(temp->right);
}

// main
int main()
{
	Node* root = CreateNode(10);
	root->left = CreateNode(11);
	root->left->left = CreateNode(7);
	root->right = CreateNode(9);
	root->right->left = CreateNode(15);
	root->right->right = CreateNode(8);

	cout << "Inorder traversal before insertion: ";
	inorder(root);
	cout << endl;

	int key = 12;
	root = InsertNode(root, key);

	cout << "Inorder traversal after insertion: ";
	inorder(root);
	cout << endl;

	return 0;
}
Code language: PHP (php)

#include<stdio.h>  
      struct node  
     {  
          int data;  
          struct node *left, *right;  
      }  
      void main()  
    {  
       struct node *root;  
       root = create();  
    }  
struct node *create()  
{  
   struct node *temp;  
   int data;  
   temp = (struct node *)malloc(sizeof(struct node));  
   printf("Press 0 to exit");  
   printf("\nPress 1 for new node");  
   printf("Enter your choice : ");  
   scanf("%d", &choice);   
   if(choice==0)  
{  
return 0;  
}  
else  
{  
   printf("Enter the data:");  
   scanf("%d", &data);  
   temp->data = data;  
   printf("Enter the left child of %d", data);  
   temp->left = create();  
printf("Enter the right child of %d", data);  
temp->right = create();  
return temp;   
}  
}  Code language: PHP (php)

Conclusion

The binary tree is one of the most widely used trees in the data structure. Each of the binary tree types has its unique features. These data structures have specific requirements in applied computer science.