A binary search tree in a data structure is typically used to represent or store hierarchical data. A “binary tree” is a tree data structure where every node has two child nodes (at the most) that form the tree branches. These child nodes are called left and right child nodes. This tutorial will help you understand the fundamental technicalities of binary trees with all the necessary details and practical examples.
What Are the Important Terms Related to Binary Trees in Data Structure?
Binary Tree is made of the root node, left-subtree, and right-subtree. The following are the components of a Binary Tree in Data Structure.
- Node: A node consists of data and links to its both child nodes
- Root: A root node is the first node of the tree
- Leaf: Nodes that don't have any children
- Parent node: Any node apart from the root node, any node with at least one child is parent to that child node
- Child node: Any node with a parent node is called a child node
- Internal node: Any node with a child and a parent
- Height: The height of a binary tree is the longest path from the root to any leaf
- Depth: A depth of a node is the total number of edges from the root node to the target node
These are the important components of binary trees. Let’s discuss the implementation of binary trees.
How Do You Implement a Binary Tree in Data Structures?
To implement a binary tree, you need to define nodes using either a structure or a class. You can utilize the following code to implement a binary tree in data structures.
Code:
//A c++ Program to implement a binary tree in data structures
#include <bits/stdc++.h>
using namespace std;
//A structure to create node
struct Node {
int data;
struct Node* left;
struct Node* right;
// A constructor to the struct node
// that inserts value in the data variable.
Node(int value)
{
data = value;
left = NULL;//Left child is initialized to NULL
right = NULL;//Right child is initialized to NULL
}
};
//A function to print the tree
void Printtree(struct Node *root)
{
//Check if tree is empty
if(root == NULL)
return;
//We will use inorder traversal to print the tree
Printtree(root -> left);
cout << root -> data << " ";
Printtree(root -> right);
}
int main()
{
// creating root
struct Node* root = new Node(1);
/*
(1)
/ \
NULL NULL
*/
root->left = new Node(2);//inserting 2 to the left of root
root->right = new Node(3);//Inserting 3 to the right of root
/*
(1)
/ \
(2) (3)
/ \ / \
NULL NULL NULL NULL
*/
root->left->left = new Node(4);//inserting 4 as left child of 2
/*
(1)
/ \
(2) (3)
/ \ / \
(4) NULL NULL NULL
*/
//function call to print the tree
Printtree(root);
return 0;
}
You now explored the implementation of binary trees, now you will see some properties of binary trees.
What Are the Properties of Binary Trees in Data Structures?
- The maximum number of nodes at level L is 2L
- Max number of Nodes in a binary tree of height H = 2H - 1
- Min possible height in a binary tree with N nodes = log2 (L+1)
- Min possible level in a binary tree with N nodes = log2 (L+1)
- A binary tree with L leaves has at least |log2 L| + 1 Levels.
What Are the Types of Binary Trees in Data Structures?
You can divide binary trees into different types based on their structure. There are five types of binary trees, they are:
Full Binary Tree
A full binary tree is a tree structure. A binary tree node can have either two children or no child.
Complete Binary Tree
A complete binary tree is another specific binary tree where each node on all levels except the last level has two children. And at the lowest level, all leaves should reside possibly on the left side.
Perfect Binary Tree
A binary tree is said to be perfect if every node must have two children and every leaf is present on the same level.
Balanced Binary Tree
Balance factor = height(left subtree) - height(right subtree)
It balances a binary tree for each node if its balance factor is either -1,0 or 1. The height of the left subtree and that of the right tree can vary by at most one.
Degenerate Binary Tree
A binary tree is referred to as a degenerate binary tree only if every internal node has exactly one child.
You looked into the different types of binary trees. Now you will see some operations you can perform on binary trees.
What Operations Can You Perform on Binary Trees in Data Structures?
You can perform two operations on a binary tree:
- Insertion
- Deletion
Now, you will look at them in detail.
How Do You Traverse a Binary Tree in Data Structures?
You can traverse binary trees in three ways:
Preorder
When you traverse a tree in a specific order, i.e., root then left subtree and then the right subtree.
Inorder
You traverse a tree from the left subtree, then root, and then to the right subtree.
Postorder
You traverse in order from the left subtree, then the right subtree, to the root.
Code:
//A c++ program to traverse a binary tree
#include<bits/stdc++.h>
using namespace std;
//A structure to create node
struct node
{
int data;
struct node *left;
struct node *right;
};
//A Function to create a new node
struct node *newNode(int data)
{
struct node *newnode = (struct node *) malloc(sizeof(struct node));
newnode -> data = data;
newnode -> left = NULL;
newnode -> right = NULL;
return newnode;
};
//A Function to insert a node in the tree
void insertnode(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case 'l' :
root -> left = newNode(n2);
break;
case 'r' :
root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}
//A Function to print the inorder traversal of the tree
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
cout << root -> data << " ";
inorder(root -> right);
}
//A function to print the preorder traversal of the tree
void preorder(struct node *root)
{
if(root == NULL)
return;
cout << root -> data << " ";
preorder(root -> left);
preorder(root -> right);
}
//A Function to print the postorder traversal of the tree
void postorder(struct node *root)
{
if(root == NULL)
return;
postorder(root -> left);
postorder(root -> right);
cout << root -> data << " ";
}
int main()
{
struct node *root = NULL;
int n;
cout <<"\nEnter the number of edges : ";
cin >> n;
cout << "\nInput the nodes of the binary tree in order \n\nparent-child-left(or)right-\n\n";
while(n--)
{
char lr;
int n1,n2;
cin >> n1 >> n2;
cin >>lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case 'l' :root -> left = newNode(n2);
break;
case 'r' : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout <<"\nInorder Traversal : ";
inorder(root);
cout << endl;
cout <<"\nPreorder Traversal : ";
preorder(root);
cout << endl;
cout <<"\nPostorder Traversal : ";
postorder(root);
cout << endl;
return 0;
}
How Do You Insert an Element Into a Binary Tree in Data Structures?
You will traverse the tree in level order until you find either a leaf or node with only the left child and then add a node.
Code:
//A c++ program to insert a node into binary tree
#include<bits/stdc++.h>
using namespace std;
//A structure to create node
struct node
{
int data;
struct node *left;
struct node *right;
};
/* Function to create a new node */
struct node *newNode(int data)
{
struct node *newnode = (struct node *) malloc(sizeof(struct node));
newnode -> data = data;
newnode -> left = NULL;
newnode -> right = NULL;
return newnode;
};
//A Function to insert a node in the tree
void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case 'l' :root -> left = newNode(n2);
break;
case 'r' : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}
//A function to print the inorder traversal of the tree */
void printtree(struct node *root)
{
if(root == NULL)
return;
printtree(root -> left);
cout << root -> data << " ";
printtree(root -> right);
}
int main()
{
struct node *root = NULL;
int n;
cout <<"\nEnter the number of edges : ";
cin >> n;
cout << "\nInput the nodes of the binary tree in order \n\nparent-child-left(or)right-\n\n";
while(n--)
{
char lr;
int n1,n2;
cin >> n1 >> n2;
cin >>lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case 'l' :root -> left = newNode(n2);
break;
case 'r' : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout <<"\nInorder Traversal : ";
printtree(root);
cout << endl;
return 0;
}
How Do You Delete an Element From a Binary Tree in Data Structures?
You will replace the extreme bottom right leave with the node you want to delete, and then delete that bottom right node.
Code:
// C++ program to delete element in binary tree
#include <bits/stdc++.h>
using namespace std;
//A structure to create node
struct Node {
int key;
struct Node *left, *right;
};
//A function to create a new node of the tree and return a pointer
struct Node* newNode(int key)
{
struct Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
};
//An Inorder traversal of a binary tree
void inorder(struct Node* temp)
{
if (!temp)
return;
inorder(temp->left);
cout << temp->key << " ";
inorder(temp->right);
}
//A function to delete the given deepest node
//(d_node) in binary tree
void deletDeepest(struct Node* root, struct Node* d_node)
{
queue<struct Node*> q;
q.push(root);
// Do level order traversal until last node
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == d_node) {
temp = NULL;
delete (d_node);
return;
}
if (temp->right) {
if (temp->right == d_node) {
temp->right = NULL;
delete (d_node);
return;
}
else
q.push(temp->right);
}
if (temp->left) {
if (temp->left == d_node) {
temp->left = NULL;
delete (d_node);
return;
}
else
q.push(temp->left);
}
}
}
//A function to delete element in binary tree
Node* deletion(struct Node* root, int key)
{
if (root == NULL)
return NULL;
if (root->left == NULL && root->right == NULL) {
if (root->key == key)
return NULL;
else
return root;
}
queue<struct Node*> q;
q.push(root);
struct Node* temp;
struct Node* key_node = NULL;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->key == key)
key_node = temp;
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
if (key_node != NULL) {
int x = temp->key;
deletDeepest(root, temp);
key_node->key = x;
}
return root;
}
int main()
{
struct Node* root = newNode(10);
root->left = newNode(11);
root->left->left = newNode(7);
root->left->right = newNode(12);
root->right = newNode(9);
root->right->left = newNode(15);
root->right->right = newNode(8);
cout << "Inorder traversal before deletion : ";
inorder(root);
int key = 11;
root = deletion(root, key);
cout << endl;
cout << "Inorder traversal after deletion : ";
inorder(root);
return 0;
}
Next Steps
"AVL Trees in data structure" can be your next stop. An AVL Tree refers to a height-balanced binary search tree. For each node, make sure that the height of the left subtree and right subtree can differ by at most one.
If you are looking to build a career in software development, explore Simplilearn's Software Development Courses, especially the Post Graduate Program in Full Stack Web Development, offered in collaboration with Caltech CTME. This online full stack bootcamp is expertly-designed to give you the work-ready software development training you need to succeed today.
If you have any questions about this “binary tree in data structures” tutorial, please feel free to leave your questions in the comments section below. Our 24/7 expert team will answer all your queries at the earliest.
