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;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	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.

delete binary search tree

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.

delete binary tree

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.

delete a bst

We move down the right subtree, which is node(6). Can we delete it? Yes we can as it’s a leaf node.

delete a binary search tree

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.

delete binary search tree

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 communications@algorithmsandme.com