.png)
In this blog, we will cover important topics related to trees but before proceeding, you should go through the following topics first as they cover the basics of Trees.
Binary Tree Traversals
Trees can be traversed in three ways, unlike linear data structures because they have only one logical way to traverse them.
Inorder (Left, Root, Right) : 2 7 5 6 11 2 5 4 9
Preorder (Root, Left, Right) : 2 7 2 6 5 11 5 9 4
Postorder (Left, Right, Root) : 2 5 11 6 7 4 9 5 2
Let's check out each of those tree traversal algorithms in details:
Inorder Traversal: In Inorder traversal, a node is processed after processing of all nodes in its left subtree. The proper subtree of the node is processed after processing the node itself.
Algorithm Inorder
1) Traverse the left subtree, i.e.,
call Inorder(left->subtree)
2) Visit the root.
3) Traverse the right subtree, i.e.,
call Inorder(right->subtree)
Example: In order traversal for the above-given tree is 2 7 5 6 11 2 5 4 9.
Preorder Traversal: In preorder traversal, a node is processed before processing any of the nodes in its subtree.
Algorithm Preorder
1) Visit the root.
2) Traverse the left subtree, i.e.,
call Preorder(left-subtree)
3) Traverse the right subtree, i.e.,
call Preorder(right-subtree) Example: Preorder traversal for the above-given tree is 2 7 2 6 5 11 5 9 4.
Postorder Traversal: In post order traversal, a node is processed after processing all of the nodes in its subtrees.
Algorithm Postorder
1) Traverse the left subtree, i.e.,
call Postorder(left-subtree)
2) Traverse the right subtree, i.e.,
call Postorder(right-subtree)
3) Visit the root.
Example: Postorder traversal for the above-given Tree is 2 5 11 6 7 4 9 5 2.
C++ program for different tree traversals:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
} node;
node *create()
{
node *p;
int x;
printf("Enter data( -1 for no node):");
scanf("%d",&x);
if(x==-1)
return NULL;
p=(node*)malloc(sizeof(node));
p->data=x;
printf("Enter left child of %d:\n",x);
p->left=create();
printf("Enter right child of %d:\n",x);
p->right=create();
return p;
}
void preorder(node *t)
{
if(t!=NULL)
{
printf(" %d",t->data);
preorder(t->left);
preorder(t->right);
}
}
void inorder(node *t)
{
if(t!=NULL)
{
inorder(t->left);
printf(" %d",t->data);
inorder(t->right);
}
}
void postorder(node *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
printf(" %d",t->data);
}
}
void main()
{
node *root;
root=create();
printf("\nThe preorder traversal of tree is: ");
preorder(root);
printf("\nThe inorder traversal of tree is: ");
inorder(root);
printf("\nThe postorder traversal of tree is: ");
postorder(root);
getch();
}Output:
Enter data( -1 for no node):90
Enter left child of 90:
Enter data( -1 for no node):12
Enter left child of 12:
Enter data( -1 for no node):34
Enter left child of 34:
Enter data( -1 for no node):-1
Enter right child of 34:
Enter data( -1 for no node):-1
Enter right child of 12:
Enter data( -1 for no node):-1
Enter right child of 90:
Enter data( -1 for no node):-1
The preorder traversal of tree is: 90 12 34
The inorder traversal of tree is: 34 12 90
The postorder traversal of tree is: 34 12 90Level Order Traversal of Binary Tree
We can also traverse a Binary Tree using the Level Order Traversal.
The binary tree is traversed level-wise starting from the first to last level sequentially in this traversal.
Consider this binary tree:
The Level Order Traversal will be 2 7 5 2 6 9 5 11 4.
Algorithm: The level Order Traversal can be implemented efficiently using a Queue.
Create an empty queue q.
Push the root node of the tree to q. That is, q.push(root).
Loop while the queue isn't empty:
Pop the top node from the queue and print the node.
Enqueue node's children (first left then right children) to q
Repeat the method until the queue isn't empty.
C++ program to print level order traversal of a Tree:
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
int data;
struct Node *left, *right;
};
// new tree node
Node* new_Node(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void print_LevelOrder(Node *root)
{
if (root == NULL) return;
//Create an empty queue for LOT
queue<Node *> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false)
{
// Print front of queue and remove
// it from queue
Node *node = q.front();
cout << node->data << " ";
q.pop();
// Enqueue left child
if (node->left != NULL)
q.push(node->left);
// Enqueue right child
if (node->right != NULL)
q.push(node->right);
}
}
int main()
{
Node *root = new_Node(10);
root->left = new_Node(20);
root->right = new_Node(30);
root->left->left = new_Node(40);
root->left->right = new_Node(50);
cout <<"Level Order traversal of binary tree is \n";
print_LevelOrder(root);
return 0;
} Output:
10 20 30 40 50Time Complexity: O(N), where N is the number of nodes in the Tree.
Auxiliary Space: O(N)
Insertion in a Binary Tree
Problem: The task is to insert the key into the binary tree at the first position available in level order. Given a binary Tree and a Key.
The idea is to apply iterative level order traversal of the given tree using a queue. We keep traversing the tree until we find a node whose either left or right child is empty.
C++ program to insert an element in a binary tree:
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int key;
struct Node* left, *right;
};
struct Node* new_Node(int key)
{
struct Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
};
void inorder(struct Node* temp)
{
if (!temp)
return;
inorder(temp->left);
cout << temp->key << " ";
inorder(temp->right);
}
void insert(struct Node* temp, int key)
{
queue<struct Node*> q;
q.push(temp);
// Do level order traversal until we find
// an empty place.
while (!q.empty()) {
struct Node* temp = q.front();
q.pop();
if (!temp->left) {
temp->left = new_Node(key);
break;
} else
q.push(temp->left);
if (!temp->right) {
temp->right = new_Node(key);
break;
} else
q.push(temp->right);
}
}
int main()
{
struct Node* root = new_Node(100);
root->left = new_Node(110);
root->left->left = new_Node(70);
root->right = new_Node(90);
root->right->left = new_Node(150);
root->right->right = new_Node(80);
cout << "Inorder traversal before insertion:";
inorder(root);
int key = 12;
insert(root, key);
cout << endl;
cout << "Inorder traversal after insertion:";
inorder(root);
return 0;
} Output:
Inorder traversal before insertion: 70 110 100 150 90 80
Inorder traversal after insertion: 70 110 120 100 150 90 80 Deletion in a Binary Tree
Problem: Our task will be to delete the given node from the binary tree.
Examples:
#1 Delete 1 in below tree
1
/ \
2 3
Output :
3
/
2
#2 Delete 2 in below tree
1
/ \
2 3
\
4
Output :
1
/ \
4 3 While performing the delete operation on binary trees, there arise a couple of cases:
The node to be deleted may be a leaf node. that's it doesn't have any children.
The node to be deleted may be an internal node. that's it has left or right child.
The node to be deleted is the root node.
In the first case 1, since the node to be deleted is a leaf node, we will simply delete the node without any overheads. But within the next 2 cases, we'll need to look out of the children of the node to be deleted.
In order to handle all of the cases, a method to delete a node is to:
Starting at the root, find the deepest and rightmost node in binary tree and node which we would like to delete.
Replace the deepest rightmost node’s data with the node to be deleted.
Then delete the deepest rightmost node.
C++ program to delete element in a binary tree :
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node* left, *right;
};
struct Node* newNode(int key)
{
struct Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
};
void inorder(struct Node* temp)
{
if (!temp)
return;
inorder(temp->left);
cout << temp->key << " ";
inorder(temp->right);
}
void delete_Deepest(struct Node *root, struct Node *d_node)
{
queue<struct Node*> q;
q.push(root);
// Do traversal until last node
struct Node* temp;
while(!q.empty())
{
temp = q.front();
q.pop();
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);
}
}
}
void deletion(struct Node* root, int key)
{
queue<struct Node*> q;
q.push(root);
struct Node *temp;
struct Node *key_node = NULL;
// Do 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);
}
int x = temp->key;
delete_Deepest(root, temp);
key_node->key = x;
}
// Driver code
int main()
{
struct Node* root = newNode(100);
root->left = newNode(110);
root->left->left = newNode(70);
root->left->right = newNode(120);
root->right = newNode(90);
root->right->left = newNode(150);
root->right->right = newNode(80);
cout << "Inorder traversal before deletion : ";
inorder(root);
int key = 11;
deletion(root, key);
cout << endl;
cout << "Inorder traversal after deletion : ";
inorder(root);
return 0;
} Output:
Inorder traversal before Deletion: 70 110 120 100 150 90 80
Inorder traversal after Deletion: 70 80 120 100 150 90Happy Coding!
Follow us on Instagram @programmersdoor
Join us on Telegram @programmersdoor
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Follow Programmers Door for more.
Comments