Delete binary search tree

delete binary search tree

Binary search tree has a unique structure with each node has two child nodes and parent node maintains pointers to both its children. This property plays an important role while designing solutions for BST problems.These problems involve deletion of complete BST, mirroring a BST, replacing parent node with sum of children etc. In next few posts we will discuss how to solve these problems with similar approach, known as bottom up approach. Once approach is mastered, most of the BST problems can be solved easily. In this post, we will discuss how to delete binary search tree. Deleting a binary search means deleting all its nodes and free up all memory allocated for that.

delete binary search tree

First mistake while thinking for solution is to delete a node as soon as it is visited. This is a blunder, because if you delete the node, we immediately lose pointers to its children. Effectively, you would be able to delete only one node, that is root node and entire tree will become unreachable which results in problem of memory leaks. So this problem gauges you understanding about structure of BST and concepts of memory leak. There are more pitfalls when we start implementing a solution.

So in order to delete a binary search tree, start with leaf nodes. Once all leaf nodes are deleted, move to upper layer which in turn would have become leaf nodes now. Continue to do so till root node and then delete root node.

This problem can easily be implemented using recursion. Why? Because to delete a tree we need to delete left and right subtree of root first. To delete those subtrees we can call the same function with parameter passed as left or right child of root, based on which subtree we are deleting.

Well, the best way to think of this problem is to consider it as post order traversal. You traverse or process (in this case delete ) left and right child of node first and then process root node. Write post order traversal code and then replace the print statement with delete node code. Done!

Algorithm to delete binary search tree

1. Start with root node.
2. If root is null, return. 
3. Check if there is left child, delete the sub tree with root as left child. 
4. Check if there is right child, delete the sub tree with root as right child. 
5. Delete the root node.

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
	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)return createNode(value);

        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;
}

Complexity of delete binary search tree is O(n) as we will be visiting each node of tree at least once.

Please share if there is something wrong or missing. If you are interested in contribute to website or have an interview experience to share, please contact us.