In the previous blog article, we discussed Tree data structure. Here, I would like to talk about a special type of tree data structure. It's about a Binary Tree. Please click here if you want to read my "Tree Data Structure" article. First, let's look at an example of a binary tree.
.png)
In a binary tree, a parent node can have only two children. That's the main characteristic of a binary tree. These binary trees are used in so many applications like implementing searching and sorting algorithms, storing data in database systems, implementing file systems, compression algorithms, etc.
Alright, let's talk about operations in a binary tree.
- Insertion - Insert a node to the binary tree
- Deletion - Delete a node from the binary tree
- Searching - Search whether an element can be found in the tree or not
- Traversal - Going through all nodes in the binary tree
We already know how to traverse a simple array. Since a binary tree is not a rival sequential data structure, we can define several ways to traverse a binary tree.
- In-order Traversal - (Left Node, Root Node, Right Node)
- Pre-order Traversal - (Root Node, Left Node, Right Node)
- Post-Order Traversal - (Left Node, Right Node, Root Node)
In-Order Traversal
In the In-order traversal, If the current node has a left child we should traverse to it. If the current node hasn't a left child then we should traverse to the current node. After that, we should traverse to the right child. Simply, First traverse the left node then traverse the root node, and after that traverse the right node. You can see it from the following video.
While you are watching following videos, stay focused only on the nodes. If you don't understand it, I recommend that you watch until understand the lesson. Also, you can pause the video and think about how it happened.
Pre-Order Traversal
Here, First, we traverse the root node. Then we traverse the left node and finally traverse the right node. Watching the following video, you can get a proper idea about pre-order traversal.
Post-Order Traversal
In the post-order traversal, First, we traverse the left node. Then we traverse the right node and finally traverse the root node. Watching the following video, you can get a proper idea about post-order traversal.
Implementation in C++
Here you can see the implementation of a complete binary tree with all operations. Before that, I want to say what is a complete binary tree. If the binary tree's parent nodes have 2 children except leaf child nodes' parents and there are no blanks among leaf nodes, we can say it's a complete binary tree. Above 3 videos I used a complete binary tree. In my code, I implement the same binary tree for your understanding.
*Reading comment lines is essential to understand the code and try these codes yourself. If you are using a mobile phone to read this, make sure to rotate your screen while reading this code.
#include <iostream>
#include <queue> // Include queue for level-order insertion and deletion
using namespace std;
// Node structure for binary tree
struct Node {
int data; // Data value of the node
Node* left; // Pointer to the left child node
Node* right; // Pointer to the right child node
// Constructor to initialize the node with a value
Node(int value) {
data = value; // Set the node's data to the given value
left = nullptr; // Initialize the left child to nullptr
right = nullptr; // Initialize the right child to nullptr
}
};
// BinaryTree class
class BinaryTree {
public:
Node* root; // Pointer to the root node of the tree
// Constructor to initialize the binary tree
BinaryTree() {
root = nullptr; // Initialize the root to nullptr
}
// Function to insert a node in level order
void insert(int value) {
if (root == nullptr) { // If the tree is empty
root = new Node(value); // Create the root node
return;
}
queue<Node*> q; // Queue for level-order traversal
q.push(root); // Start with the root node
while (!q.empty()) { // While there are nodes to process
Node* temp = q.front(); // Get the front node in the queue
q.pop(); // Remove it from the queue
if (temp->left == nullptr) { // If the left child is empty
temp->left = new Node(value); // Insert the new node here
break; // Exit the loop
} else {
q.push(temp->left); // Otherwise, add left child to the queue
}
if (temp->right == nullptr) { // If the right child is empty
temp->right = new Node(value); // Insert the new node here
break; // Exit the loop
} else {
q.push(temp->right); // Otherwise, add right child to the queue
}
}
}
// Function for inorder traversal
void inorder() {
inorderRec(root); // Call the recursive inorder traversal function
cout << endl; // Print a newline at the end
}
// Function for preorder traversal
void preorder() {
preorderRec(root); // Call the recursive preorder traversal function
cout << endl; // Print a newline at the end
}
// Function for postorder traversal
void postorder() {
postorderRec(root); // Call the recursive postorder traversal function
cout << endl; // Print a newline at the end
}
// Function to delete a node
void deleteNode(int value) {
if (root == nullptr) { // If the tree is empty
return; // Nothing to delete
}
if (root->left == nullptr && root->right == nullptr) { // If the tree has only one node
if (root->data == value) { // And it's the node to delete
delete root; // Delete the root node
root = nullptr; // Set the root to nullptr
}
return; // Exit the function
}
queue<Node*> q; // Queue for level-order traversal
q.push(root); // Start with the root node
Node* temp; // Pointer to traverse the tree
Node* keyNode = nullptr; // Pointer to the node to be deleted
// Level order traversal to find the deepest node and the node to be deleted
while (!q.empty()) {
temp = q.front(); // Get the front node in the queue
q.pop(); // Remove it from the queue
if (temp->data == value) { // If this is the node to be deleted
keyNode = temp; // Save the pointer to this node
}
if (temp->left != nullptr) { // If there is a left child
q.push(temp->left); // Add it to the queue
}
if (temp->right != nullptr) { // If there is a right child
q.push(temp->right); // Add it to the queue
}
}
if (keyNode != nullptr) { // If the node to be deleted was found
int x = temp->data; // Save the data from the deepest node
deleteDeepest(temp); // Delete the deepest node
keyNode->data = x; // Replace the data of the node to be deleted
}
}
private:
// Helper function for inorder traversal recursively
void inorderRec(Node* node) {
if (node == nullptr) { // If the node is null
return; // Return without doing anything
}
inorderRec(node->left); // Recursively traverse the left subtree
cout << node->data << " "; // Print the current node's data
inorderRec(node->right); // Recursively traverse the right subtree
}
// Helper function for preorder traversal recursively
void preorderRec(Node* node) {
if (node == nullptr) { // If the node is null
return; // Return without doing anything
}
cout << node->data << " "; // Print the current node's data
preorderRec(node->left); // Recursively traverse the left subtree
preorderRec(node->right); // Recursively traverse the right subtree
}
// Helper function for postorder traversal recursively
void postorderRec(Node* node) {
if (node == nullptr) { // If the node is null
return; // Return without doing anything
}
postorderRec(node->left); // Recursively traverse the left subtree
postorderRec(node->right); // Recursively traverse the right subtree
cout << node->data << " "; // Print the current node's data
}
// Helper function to delete the deepest node
void deleteDeepest(Node* delNode) {
queue<Node*> q; // Queue for level-order traversal
q.push(root); // Start with the root node
Node* temp; // Pointer to traverse the tree
while (!q.empty()) {
temp = q.front(); // Get the front node in the queue
q.pop(); // Remove it from the queue
if (temp == delNode) { // If this is the node to delete
temp = nullptr; // Nullify the pointer
delete delNode; // Delete the node
return; // Exit the function
}
if (temp->right) { // If there is a right child
if (temp->right == delNode) { // If it is the node to delete
temp->right = nullptr; // Nullify the right child pointer
delete delNode; // Delete the node
return; // Exit the function
} else {
q.push(temp->right); // Otherwise, add it to the queue
}
}
if (temp->left) { // If there is a left child
if (temp->left == delNode) { // If it is the node to delete
temp->left = nullptr; // Nullify the left child pointer
delete delNode; // Delete the node
return; // Exit the function
} else {
q.push(temp->left); // Otherwise, add it to the queue
}
}
}
}
};
int main() {
BinaryTree tree; // Create a BinaryTree object
tree.insert(10); // Insert nodes into the tree
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(60);
tree.insert(70);
tree.insert(80);
tree.insert(90);
tree.insert(100);
cout << "Inorder traversal: ";
tree.inorder(); // Perform and print inorder traversal
cout << "Preorder traversal: ";
tree.preorder(); // Perform and print preorder traversal
cout << "Postorder traversal: ";
tree.postorder(); // Perform and print postorder traversal
cout << "Deleting node 30" << endl;
tree.deleteNode(30); // Delete the node with value 30
cout << "Inorder traversal after deletion: ";
tree.inorder(); // Perform and print inorder traversal after deletion
return 0; // Return 0 to indicate successful execution
}
Output of the above code
Inorder traversal: 80 40 90 20 100 50 10 60 30 70
Preorder traversal: 10 20 40 80 90 50 100 30 60 70
Postorder traversal: 80 90 40 100 50 20 60 70 30 10
Deleting node 30
Inorder traversal after deletion: 80 40 90 20 50 10 60 100 70
Advantages
- Ordered Traversal (In-Order, Pre-Order, Post-Order)
- Memory Efficient
- Efficient Searching
- Fast Insertion and Deletion
- Useful for Sorting
Disadvantages
- Limited Structure
- Space Inefficiency
- Slow performance in worst-case scenarios (Time complexities will be discussed in the Binary Search Tree article)
- Unbalance Trees - by inserting data in a non-random order.
Conclusion
In this entire article, I talked about Binary Trees, its operations, and also its advantages and disadvantages. In the next article, I would like to discuss Binary Search Trees, which are a type of binary tree. If you think this is valuable, please share this with your friends. Thank you for reading this and have a nice day!
