Tags: , , , ,

# Delete binary search tree

In last post Binary search tree traversals we discussed various kind of traversals of tree like inorder, preorder and post order traversals. One of the many problems which can be solved using these traversals is to delete binary search tree. Problem is : given a binary search tree, delete all nodes of it.

## Delete binary tree : Thoughts

As always, we would start from the root of the binary tree. What choice do we have here? We can delete the root node immediately. We can delete left subtree first and then delete root node. Or we can delete left subtree, right subtree and then delete the node.
If we delete root node immediately, we lose access to left and right subtree as root node contains references to these. Deletion of root upfront would have been preorder traversal.

If we delete root node after deleting left subtree, we lose reference to right subtree. So, we can not delete root node before deleting both left and right subtree. That means we will be processing root node last. What kind of traversal is that? Of course postorder traversal, instead of print node, delete node.

Recursive nature of problem is evident that to delete a tree, we have to first delete the subtree and then it’s subtree and so on.

### Delete binary search tree : Implementation

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

void deleteBST(Node *root){
if(!root)
return ;

//Process left subtree
deleteBST(root->left);
//Process right subtree
deleteBST(root->right);
//Free the root node
root->left = NULL;
root->right = NULL;
free(root);
}

Node * createNode(int value){
Node * newNode =  (Node *)malloc(sizeof(Node));
newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;
}
if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree

deleteBST(root);

return 0;
}
```

Java implementation

```package com.company.BST;

import java.util.ArrayList;

/**
* Created by sangar on 10.5.18.
*/
public class BinarySearchTree {

private Node root;

public void BinarySearchTree(){
root = null;
}

public class Node {
private int value;
private  Node left;
private Node right;

public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}

public void insert(int value){
this.root =  insertNode(this.root, value);
}

private Node insertNode(Node root, int value){
if(root == null){
//if this node is root of tree
root = new Node(value);
}
else{
if(root.value > value){
/*If root is greater than value, node
should be added to left subtree */
root.left = insertNode(root.left, value);
}
else{
/* If root is less than value, node
should be added to right subtree */
root.right = insertNode(root.right, value);
}
}
return root;
}

public void delete(){
deleteRecusrive(this.root);
this.root = null;
}
private void deleteRecusrive(Node root){
if(root == null) return;

//delete left subtree
deleteRecusrive(root.left);
//delete right subtree
deleteRecusrive(root.right);

//delete the root, which will be collected by GC
root.left = null;
root.right = null;
}
}
```

Test class

```package com.company.BST;

/**
* Created by sangar on 10.5.18.
*/
public class BinarySearchTreeTests {
public static void main (String[] args){
BinarySearchTree binarySearchTree = new BinarySearchTree();

binarySearchTree.insert(7);
binarySearchTree.insert(8);
binarySearchTree.insert(6);
binarySearchTree.insert(9);
binarySearchTree.insert(3);
binarySearchTree.insert(4);

binarySearchTree.delete();
binarySearchTree.inorderTraversal();
}
}

```
##### Delete binary search tree : Example

Let’s see how it works. Given below binary search tree, we have to delete it. We start with `node(10)`, can we delete it? No we cannot because there is left subtree and right subtree attached to it. Move down the `node(5)`, and check if it can be deleted. No as  it has left and right child. Again, we move down to left subtree, and new candidate for deletion is `node(1)`. Can we delete it? Yes as it is leaf node with no left or right child. After deleting `node(1)`, we move back to it’s parent `node(5)`, we cannot still delete `node(5)` as there is right subtree to it. We move down the right subtree, which is `node(6)`. Can we delete it? Yes we can as it’s a leaf node. Once, we delete `node(6)`, new candidate for deletion is again `node(5)`.  Can we delete node(5) now? Yes as we already deleted left and right subtree of the node, we can safely delete it. After deleting `node(5)`, we move up to it’s parent which is `node(10)`. Can we delete it? No as there is right subtree to it. Our new candidate for deletion is `node(19)`, can we delete it? Nope, as it has left and right subtree to it. Move down the left subtree and candidate is `node(17)`. Delete node(17) and move up to the parent `node(19)`, however, do not delete `node(19)` still as there is right child of it. Now, move down to `node(21)`. Delete `node(21)` as it is leaf node. After deleting `node(21)`, we move up to parent which is `node(19)`. Can `node(19)` be delete now? Yes as left and right subtree have been deleted, parent node can be deleted safely. Same as other nodes, delete `node(10)` too. Complexity of algorithm to delete binary search tree is `O(n)` as we scan all the nodes of tree at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us on [email protected]