EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Binary Tree Deletion
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Binary Tree Deletion

Binary Tree Deletion

Introduction to Binary Tree Deletion

Binary tree deletion is known as the delete a node from the binary tree. Delete a node from a binary tree shrinks the tree from the rightmost bottom. That means if you delete a node from a binary tree, it will be replaced by the rightmost bottom node. This deletion is something different from the binary search tree. Unlike the binary search tree, the binary tree does not have any order; that’s why we replace delete a node from the rightmost bottom node. To delete a node, first, we will start from the root and go for the rightmost bottom node. Then we will search the node which we want to delete and replace it with the rightmost bottom node. Then finally, we will delete the rightmost bottom node.

Syntax of Binary Tree Deletion

Given below is the syntax mentioned:

void deleteNode(Node *root, int data)
{
if(root == NULL)
{
Cout << “Tree is empty\n”;
return;
}
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node *temp = q.front();
q.pop();
if(temp->data == data)
{
Node *current = root;
Node *prev;
while(current->right != NULL)
{
prev = current;
current = current->right;
}
temp ->data = current->data;
prev->right = NULL;
free(current);
cout << “Deleted\n”;
return;
}
if(temp->left != NULL)
q.push(temp->left);
if(temp->right != NULL)
q.push(temp->right);
}
cout << “Node not found for deletion\n”;
}

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Binary Tree Traversal

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal.

We will consider several traversal algorithms with a group in the following two kinds:

  • depth-first traversal
  • breadth-first traversal

There are three different types of depth-first traversal:

  • PreOdrer traversal: Visit the parent first and then the left and right child.
  • InOrder traversal: Visit the left child, then the parent and the right child.
  • PostOrder traversal: Visit the left child, then the right child and then the parent.

There is only one kind of breadth-first traversal: The level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.

How to Perform Binary Tree Deletion?

To perform binary tree deletion, first, we will maintain a queue and use the push root node into it. Then, while q is not empty, we will do the processing. Let’s say we keep two pointers, key_node denoted as Node*, NULL pointer and last node or deepest node.

Now, we will pick one element, let’s say the current node and the current node will always be the element that we pop from the queue. We will check if this value matches with the key which we want to delete. Every node has some data of some data type, then left and right pointers. So we will compare this data of the current node with the deletion key; if it matches, then we will update key_node. So, if the current node data is equal to the key, then the key node is equal to the current node. When this loop ends, the queue is empty, and every node has been processed. So whatever was the last value of last_node, that will denote the leaf node of the tree.

Algorithm For Binary Tree Deletion

Given below is the algorithm of Binary Tree Deletion:

Algorithm Bideletionseq(key)
{
//key is node to be deleted

l = BTSearchseq(i, key);
if((A[2*l] == NULL) && A[2*l +1] == NULL) then
A[l] = NULL;
else
printf(“the node not present”);
}

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,408 ratings)

Algorithm Bideletionlink(item)
{
//item is a data to be deleted
Parent = BTSearchlink(root, item);
{
if(parent→lchild != NULL && parent→rchild != NULL)
{
ptr1 = parent→lchild;
ptr2 = parent→rchild;
if(ptr1→child == NULL && ptr1→ rchild == NULL)
{
ptr1→lchild = NULL;
}
if(ptr2→ lchild == NULL && ptr2→rchild == NULL) then
{
ptr2→rchild = NULL;
}
}
else
printf(“deletion is not possible”);
}

Example:

1
/ \
2 3
/ /
4 5
\
6

So this is the binary tree in which we have to delete node with data 3 in the inorder traversal.

Code for deletion in C++:

#include<iostream>
#include<queue>
using namespace std;
struct Node{
int data;
Node *left;
Node *right;
Node(int val): data(val), left(NULL), right(NULL){}
~Node(){}
};
void inorder(Node *root){
if(!root){
return;
}
inorder(root->left);
std::cout<<root->data<<"\t";
inorder(root->right);
}
void remove_node(Node *root, Node *n){
if(root == NULL)
return;
if(root == n){
delete n;
root = NULL;
return;
}
if(root->left == n){
delete n;
root->left = NULL;
return;
}
if(root->right == n){
delete n;
root->right = NULL;
return;
}
remove_node(root->left, n);
remove_node(root->right, n);
}
Node* delete_node(Node *root, int key){
if(root == NULL)
return NULL;
if(!root->left && !root->right){
if(root->data == key){
delete root;
root = NULL;
return root;
}
return root;
}
std::queue<Node *>Q;
Q.push(root);
Node *key_node = NULL;
Node *curr_node = NULL;
while(!Q.empty()){
curr_node = Q.front();
Q.pop();
if(curr_node->data == key){
key_node = curr_node;
}
if(curr_node->left)
Q.push(curr_node->left);
if(curr_node->right)
Q.push(curr_node->right);
}
if(key_node){
key_node->data = curr_node->data;
remove_node(root, curr_node);
}
return root;
}
int main(){
Node *n1 = new Node(1);
Node *n2 = new Node(2);
Node *n3 = new Node(3);
Node *n4 = new Node(4);
Node *n5 = new Node(5);
Node *n6 = new Node(6);
n1->left = n2;
n1->right = n3;
n2->left = n4;
n3->left = n5;
n4->right = n6;
Node *root = n1;
inorder(root);
std::cout<<endl;
root = delete_node(root, 3);
inorder(root);
std::cout<<endl;
return 0;
}

Output:

Binary Tree Deletion

Advantages of Binary Tree

Trees are so useful and frequently used because they have some very serious advantages:

  • First, trees reflect structural relationships in the data.
  • Second, trees are used to represent hierarchies.
  • Third, trees provide an efficient insertion and searching.
  • Finally, trees are very flexible data, allowing to move.
  • Subtrees around with minimum effort.

Conclusion

After this article, we now know about the binary tree, and the traversal theory in a binary tree means how we travel in the binary tree. How we delete a node in a binary tree, its syntax, code in C++ language, and give an example to easily understand the deletion of a node in a binary tree.

Recommended Articles

This is a guide to Binary Tree Deletion. Here we discuss the introduction, how to perform binary tree deletion? algorithm and advantages, respectively. You may also have a look at the following articles to learn more –

  1. Binary Tree Program in C
  2. Inorder Traversal of Binary Tree
  3. Binary Tree in Data Structure
  4. Tree Traversal Techniques
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (7 Courses, 8+ Projects)4.7
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more