Question

Using the following definitions for a binary tree,

typedef struct bintreenode

{

    int data;

    struct bintreenode* left;

    struct bintreenode* right;

} btreenode;

// Used for a node in the queue.

typedef struct node

{

    btreenode* nodePtr;

    struct node* next;

} node;

// Used to represent the queue efficiently.

typedef struct queue

{

    node* front;

    node* back;

} queue;

Implement the following functions:

void bfs(btreenode* root) // Prints a breadth first search traversal of the binary search tree rooted at root.

void insert(btreenode* root, int value) //using level order

void deletion(btreenode* root, int value) // find the node to be deleted and also the deepest node, copy the value of the deepest node to the node to be deleted

void deleteDeepest(btreenode* root, btreenode* d_node) // delete the deepest node  

Answer 1

CODE:-

void bfs(btreenode* root)
{
   if (root == NULL) return;
queue<btreenode *> q;
q.push(root);
  
while (q.empty() == false)
{
btreenode *temp = q.front();
cout << temp->data << " ";
q.pop();
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
}
void insert(btreenode* root, int value)
{
// If the tree is empty, assign new node address to root
btreenode* newNode = new btreenode();
if (root == NULL) {
       newNode->data = value;
newNode->left = newNode->right = NULL;
root = newNode;
return root;
}

queue<btreenode*> q;
q.push(root);

while (!q.empty()) {
btreenode* temp = q.front();
q.pop();

if (temp->left != NULL)
q.push(temp->left);
else {
           newNode->data = value;
newNode->left = newNode->right = NULL;
temp->left = newNode;
return ;
}

if (temp->right != NULL)
q.push(temp->right);
else {
       newNode->data = value;
newNode->left = newNode->right = NULL;
temp->right = newNode;
return ;
}
}
}
void deletion(btreenode* root, int value)
{
if (root == NULL)
return NULL;
  
if (root->left == NULL && root->right == NULL) {
if (root->data == key)
return NULL;
else
return root;
}
  
queue<btreenode*> q;
q.push(root);
  
btreenode* temp;
btreenode* key_node = NULL;
while (!q.empty()) {
temp = q.front();
q.pop();
  
if (temp->data == value)
key_node = temp;
  
if (temp->left)
q.push(temp->left);
  
if (temp->right)
q.push(temp->right);
}
  
if (key_node != NULL) {
int x = temp->key;
deletDeepest(root, temp);
key_node->key = x;
}
}
void deleteDeepest(btreenode* root,
btreenode* d_node)
{
queue <btreenode*>q;
q.push(root);
  
// Do level order traversal until last node
bintreenode* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == d_node) {
temp = NULL;
delete (d_node);
return;
}
if (temp->right) {
if (temp->right == d_node) {
temp->right = NULL;
delete (d_node);
return;
}
else
q.push(temp->right);
}
  
if (temp->left) {
if (temp->left == d_node) {
temp->left = NULL;
delete (d_node);
return;
}
else
q.push(temp->left);
}
}
}

Explanation:-

1)BFS on a tree is simply level order traversal the idea is to push the root in the queue then it’s child nodes are also put in the First In First Out queue then we’re printing the nodes in level order traversal.
2) In this approach we traverse the tree in level order using a queue and then check if any node whose left child is empty then we insert our new node here and like this we also check the right child of any node if it is empty then we insert our new node.
3) Here the algorithm is to find the deepest rightmost element and we replace it’s data with the data of the node to be deleted and then we delete the deepest rightmost element.