Answer to Question #278566 in C++ for Muhammad Ahsan

Question

Write down functions to:

Insert and remove a binary tree.

Answer 1

#include <bits/stdc++.h>
using namespace std;
class nodeInTree{
   public:
      int value;
      nodeInTree *left, *right;
      nodeInTree(int x){
         val = x;
         left = right = NULL;
      }
};
void insert(nodeInTree **root, int value){
   Queue<nodeInTree*> Q;
   Q.push(*root);
   while(Q.size()){
      nodeInTree *temp = Q.front();
      Q.pop();
      if(!temp->left){
         if(value != NULL)
            temp->left = new nodeInTree(value);
         else
            temp->left = new nodeInTree(0);
         return;
      }
      else{
         Q.push(temp->left);
      }
      if(!temp->right){
         if(value != NULL)
            temp->right = new nodeInTree(value);
         else
            temp->right = new nodeInTree(0);
         return;
      }
      else{
         Q.push(temp->right);
      }
   }
}
nodeInTree *make_tree(vector<int> v){
   nodeInTree *root = new nodeInTree(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
void tree_level_trav(nodeInTree*root){
   if (root == NULL) return;
      cout << "[";
   Queue<nodeInTree *> Q;
   nodeInTree *curr;
   Q.push(root);
   Q.push(NULL);
   while (Q.size() > 1) {
      curr = Q.front();
      Q.pop();
      if (curr == NULL){
         Q.push(NULL);
      }
      else {
         if(curr->left)
            Q.push(curr->left);
         if(curr->right)
            Q.push(curr->right);
         if(curr->value == 0 || curr == NULL){
            cout << "null" << ", ";
         }
         else{
            cout << curr->value << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   nodeInTree* insertIntoTree(nodeInTree* root, int value) {
      if(!root)return new nodeInTree(value);
      if(root->value > value){
         root->left = insertIntoTree(root->left, value);
      }
      else root->right = insertIntoTree(root->right, value);
         return root;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,2,7,1,3};
   nodeInTree *root = make_tree(v);
   tree_level_trav(ob.insertIntoTree(root, 5));
}

Remove

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int key;
    struct Node *left, *right;
};
struct Node* newNodeInTheTree(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
void inorder(struct Node* temp)
{
    if (!temp)
        return;
    inorder(temp->left);
    cout << temp->key << " ";
    inorder(temp->right);
}
void deletDeepest(struct Node* root,
                  struct Node* d_node)
{
    Queue<struct Node*> Q;
    Q.push(root);
    struct Node* 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);
        }
    }
}
Node* deletion(struct Node* root, int key)
{
    if (root == NULL)
        return NULL;
 
    if (root->left == NULL && root->right == NULL) {
        if (root->key == key)
            return NULL;
        else
            return root;
    }
    Queue<struct Node*> Q;
    Q.push(root);
    struct Node* temp;
    struct Node* key_node = NULL;
    while (!Q.empty()) {
        temp = Q.front();
        Q.pop();
 
        if (temp->key == key)
            key_node = temp;
 
        if (temp->left)
            Q.push(temp->left);
 
        if (temp->right)
            Q.push(temp->right);
    }
    if (key_node != NULL) {
        int y = temp->key;
        deletDeepest(root, temp);
        key_node->key = y;
    }
    return root;
}
int main()
{
    struct Node* root = newNodeInTheTree(10);
    root->left = newNodeInTheTree(11);
    root->left->left = newNodeInTheTree(7);
    root->left->right = newNodeInTheTree(12);
    root->right = newNodeInTheTree(9);
    root->right->left = newNodeInTheTree(15);
    root->right->right = newNodeInTheTree(8);
    cout << "Inorder traversal before deletion in the binary : ";
    inorder(root);
    int key = 11;
    root = deletion(root, key);
    cout << endl;
    cout << "Inorder traversal after deletion in the binary tree: ";
    inorder(root);
    return 0;
}