Question

7) Given a binary search tree, insert a new node with specific data such that the binary tree after the insertion is also a binary search tree.

8) Given a binary search tree, delete a node with a specific data value such that the binary tree after the deletion is also a binary search tree.

reply in c++

Answer 1

#include<iostream>
#include<stdlib.h>
using namespace std;
//structure of Binary Search Tree
struct BST
{
int val;
BST *left, *right;
};

//method to create a new node
BST *newNode(int num)
{
//BST *T = (BST *)malloc(sizeof(BST)); //allocate a new node
BST *T = new BST;
T->val = num;
T->left = T->right = NULL;
return T;
}

//inorder traversal
void inorder(BST *root)
{
if (root != NULL)
{ //move left
inorder(root->left);
cout<<" "<<root->val; //print the value
//move right
inorder(root->right);
}
}

//this function will insert the elements into the tree
BST * insert(BST * node, int x)
{
//condition for Empty tree
if (node == NULL) return newNode(x);
  
//if element is less than the tree value then move left
if (x < node->val)
node->left = insert(node->left, x);
//if element is greater than the tree value then move right
else if (x > node->val)
node->right = insert(node->right, x);
//return the node
return node;
}

// Driver Program
int main()
{
  
BST *root = NULL;
int i,n,no;
//ask user about the number of elements
cout<<endl<<"Enter the number of elements of a tree";
cin>>n;//read the number
//enter the value of root node
cout<<endl<<"Enter the value of root node";
cin>>no;
//insert the root node
root = insert(root,no);
//loop to insert the other nodes
for(i=2;i<=n;i++)
{
   cout<<endl<<"Enter a number";
   cin>>no;
   insert(root, no);
   }
// Inorder traversal of tree
inorder(root);
//ask user to input an extra element into the tree
cout<<endl<<"Enter a number to insert an element with the tree";
cin>>no;
//insert the extra element
insert(root, no);
//print the tree after insertion
cout<<endl<<"After insertion of the element the tree is ";
inorder(root);
return 0;
}

output

8)

#include<iostream>
#include<stdlib.h>
using namespace std;
//structure of Binary Search Tree
struct BST
{
int val;
BST *left, *right;
};

//method to create a new node
BST *newNode(int num)
{
//BST *T = (BST *)malloc(sizeof(BST)); //allocate a new node
BST *T = new BST;
T->val = num;
T->left = T->right = NULL;
return T;
}

//inorder traversal
void inorder(BST *root)
{
if (root != NULL)
{ //move left
inorder(root->left);
cout<<" "<<root->val; //print the value
//move right
inorder(root->right);
}
}

//this function will insert the elements into the tree
BST * insert(BST * node, int x)
{
//condition for Empty tree
if (node == NULL) return newNode(x);
  
//if element is less than the tree value then move left
if (x < node->val)
node->left = insert(node->left, x);
//if element is greater than the tree value then move right
else if (x > node->val)
node->right = insert(node->right, x);
//return the node
return node;
}

BST * min(BST * node)
{
BST * current = node;
  
/* loop down to find the leftmost leaf */
while (current && current->left != NULL)
current = current->left;
  
return current;
}
  
//METHOD TO DELETE THE NODE FROM TREE
BST * Delete(BST * root, int x)
{
//CONDITION FOR NULL TREE
if (root == NULL) return root;
  
//IF THE node to be delete is less than root then move left
if (x < root->val)
root->left = Delete(root->left, x);
  
//IF THE node to be delete is less than root then move right
else if (x > root->val)
root->right = Delete(root->right, x);
//this node will delete
else
{
// node with only one child or no child
if (root->left == NULL)
{
BST *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
BST *temp = root->left;
free(root);
return temp;
}
  
// node with two children
BST * temp = min(root->right);
  
  
root->val = temp->val;

root->right = Delete(root->right, temp->val);
}
return root;
}

// Driver Program
int main()
{
  
BST *root = NULL;
int i,n,no;
//ask user about the number of elements
cout<<endl<<"Enter the number of elements of a tree";
cin>>n;//read the number
//enter the value of root node
cout<<endl<<"Enter the value of root node";
cin>>no;
//insert the root node
root = insert(root,no);
//loop to insert the other nodes
for(i=2;i<=n;i++)
{
   cout<<endl<<"Enter a number";
   cin>>no;
   insert(root, no);
   }
// Inorder traversal of tree
inorder(root);

//ask user to DELETE an element into the tree
cout<<endl<<"Enter a number to delete an element with the tree";
cin>>no;
//delete an element
Delete(root, no);
//print the tree after deletion
cout<<endl<<"After deletion of the element the tree is ";
inorder(root);
return 0;
}

output