A One-Stop Solution For Using Binary Search Trees In Data Structure

Code:

// A c++ program to perform insertion in binary search tree.

#include <bits/stdc++.h>

using namespace std;

// A class to create node

class Binarysearchtree

{

int data;

Binarysearchtree *left, *right;

public:

// Default constructor.

Binarysearchtree();

// Parameterized constructor.

Binarysearchtree(int);

// Insert function.

Binarysearchtree* Insert(Binarysearchtree*, int);

// Inorder traversal.

void Inorder(Binarysearchtree*);

};

// Default Constructor definition.

Binarysearchtree ::Binarysearchtree()

: data(0)

, left(NULL)

, right(NULL)

{

}

// Parameterized Constructor definition.

Binarysearchtree ::Binarysearchtree(int data1)

{

data = data1;

left = right = NULL;

}

// Insert function definition.

Binarysearchtree* Binarysearchtree ::Insert(Binarysearchtree* root, int data1)

{

if (!root)

{

//we will insert the first node, if root is NULL.

return new Binarysearchtree(data1);

}

// Insert data.

if (data1> root->data)

{

// Insert right node data, if the 'data1'

// to be inserted is larger than 'root' node data.

// Process right nodes.

root->right = Insert(root->right, data1);

}

else

{

// Insert left node data, if the 'data1'

// to be inserted is larger than 'root' node data.

// Process left nodes.

root->left = Insert(root->left, data1);

}

// Return 'root' node, after insertion.

return root;

}

// Inorder traversal function.

// This gives data in sorted order.

void Binarysearchtree ::Inorder(Binarysearchtree* root)

{

if (!root) {

return;

}

Inorder(root->left);

cout << root->data << “ ”;

Inorder(root->right);

}

// Driver code

int main()

{

Binarysearchtree bst, *root = NULL;

root = bst.Insert(root, 5);

bst.Insert(root, 3);

bst.Insert(root, 2);

bst.Insert(root, 4);

bst.Insert(root, 7);

bst.Insert(root, 6);

bst.Insert(root, 8);

cout<<"created Binary search tree: \n";

bst.Inorder(root);

return 0;

}

Code: 

// A C++ program to perform deletion on a BST

#include <bits/stdc++.h>

using namespace std;

struct node {

int data;

struct node *left, *right;

};

// A function to create a BST node

struct node* newNode(int key)

{

struct node* temp

= (struct node*)malloc(sizeof(struct node));

temp->data = key;

temp->left = temp->right = NULL;

return temp;

}

// A function to display BST

void display(struct node* root)

{

if (root != NULL) {

display(root->left);

cout << root->data<<" ";

display(root->right);

}

}

// A function to insert a node in the binary search tree

struct node* insert(struct node* newnode, int data)

{

// If the tree is empty, we will return a new node 

if (newnode == NULL)

return newNode(data);

/* Otherwise, recur down the tree */

if (data < newnode->data)

newnode->left = insert(newnode->left, data);

else

newnode->right = insert(newnode->right, data);

return newnode;

}

// A function returns the node with the minimum data value found in that tree.

struct node* minvalue(struct node* node)

{

struct node* temp = node;

while (temp && temp->left != NULL)

temp= temp->left;

return temp;

}

// A function to perform deletion on BST 

struct node* deleteNode(struct node* root, int data)

{

// base case

if (root == NULL)

return root;

// If the element to be deleted is smaller than the root's data, then it lies in left subtree

if (data < root->data)

root->left = deleteNode(root->left, data);

// If the element to be deleted is greater than the root's data, then it lies in right subtree

else if (data > root->data)

root->right = deleteNode(root->right, data);

// if data is same as root's data, then This is the node

// to be deleted

else {

// node has no child

if (root->left==NULL and root->right==NULL)

return NULL;

// node with either one child or no child

else if (root->left == NULL) {

struct node* t = root->right;

free(root);

return t;

}

else if (root->right == NULL) {

struct node* t = root->left;

free(root);

return t;

}

// for a node with two children, we will get the inorder successor

struct node* t = minvalue(root->right);

root->data = t->data;

// Delete the inorder successor

root->right = deleteNode(root->right, t->data);

}

return root;

}

int main()

{

// lets create an empty binary search tree

struct node* root = NULL;

root = insert(root, 5);

root = insert(root, 3);

root = insert(root, 2);

root = insert(root, 4);

root = insert(root, 7);

root = insert(root, 6);

root = insert(root, 8);

cout << "Original Binary search tree: \n";

display(root);

cout << "\n\nDelete 2\n\n";

root = deleteNode(root, 2);

cout << "modified binary search tree \n";

display(root);

cout << "\n\nDelete 5\n\n";

root = deleteNode(root, 5);

cout << "modified binary search tree \n";

display(root);

return 0;

}