Binary Search Tree (BST)

Binary Search Tree

Binary Search Tree (BST) is a node-based binary tree data structure having the following properties:

1. The left subtree of a node contains only nodes with keys less than the node’s key.

1. The right subtree of a node contaisns only nodes with greater than the node’s Key.

1. The left and right subtree each must also be a binary search tree.

BST has some basic operation like Search, Insert, Delete, Traversal (In-order, pre-order, post-order).If we want to delete a node from BST, Firstly we search this node and delete this node.

Now we make a BST using some data and following the BST properties. The data is given below:

                 47,40,54,38,30,39,49,60,57,80;

	#include<bits/stdc++.h>
	using namespace std;
	struct bst
	{
	int number;
	bst *left, *right;
	};
	bst *root = NULL;
	void Insert(int val);
	void In_order(bst *root);
	bst *Find_Min(bst *root);
	bst *Delete(bst *root, int val);
	int main()
	{
	/*
	10
	47 40 54 38 30 39 49 60 57 80
	*/
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
	int x;
	scanf("%d", &x);
	Insert(x);
	}
	printf("\nIn-Order BST printing:\n");
	In_order(root);
	printf("\n");
	int delete_node = 57;
	root = Delete(root, delete_node);
	printf("\nIn-Order BST printing after %d deletion: \n", delete_node);
	In_order(root);
	printf("\n");
	delete_node = 40;
	root = Delete(root, delete_node);
	printf("\nIn-Order BST printing after %d deletion: \n", delete_node);
	In_order(root);
	printf("\n");
	delete_node = 47;
	root = Delete(root, delete_node);
	printf("\nIn-Order BST printing after %d deletion: \n", delete_node);
	In_order(root);
	printf("\n");
	return 0;
	}
	void Insert(int val)
	{
	bst *temp;
	bst *current;
	bst *parent;
	temp = new bst;
	temp->number = val;
	temp->left = NULL;
	temp->right = NULL;
	if(root==NULL)
	{
	root = temp;
	}
	else
	{
	current = root;
	parent = NULL;
	while(1)
	{
	parent = current;
	if(val <= parent->number)
	{
	current = current->left;
	if(current==NULL)
	{
	parent->left = temp;
	return;
	}
	}
	else
	{
	current = current->right;
	if(current==NULL)
	{
	parent->right = temp;
	return;
	}
	}
	}
	}
	}
	void In_order(bst *root)
	{
	if(root==NULL)
	return;
	In_order(root->left);
	printf("%d ", root->number);
	In_order(root->right);
	}
	bst *Delete(bst *current, int val)
	{
	if(current == NULL)return NULL;
	else if(val < current->number)
	current->left = Delete(current->left, val);
	else if(val > current->number)
	current->right = Delete(current->right, val);
	else
	{
	if(current->left == NULL && current->right == NULL)
	{
	current = NULL;
	}
	else if(current->left == NULL)
	{
	current = current->right;
	}
	else if(current->right == NULL)
	{
	current = current->left;
	}
	else
	{
	bst *temp = Find_Min(current->right);
	current->number = temp->number;
	current->right = Delete(current->right, temp->number);
	}
	}
	return current;
	}
	bst *Find_Min(bst *current)
	{
	if(current->left==NULL)
	return current;
	return Find_Min(current->left);
	}

view raw bst.cpp hosted with ❤ by GitHub

Share: