Answers for "bst with parent pointer"

C++
0

bst with parent pointer

#include<iostream>
#include<queue>

using namespace std;

struct Node {
      int data;
      Node *left, *right, *parent;
};

struct Node *newNode(int data) {
   Node *temp = new Node;
   temp->data = data;
   temp->left = temp->right = temp->parent = NULL;
   return temp;
}
void inorderTraverse(struct Node *root) {
   if (root != NULL)  {
    // Traverse left
    inorderTraverse(root->left);

    // Traverse root
    printf("%d -> ", root->data);

    // Traverse right
    inorderTraverse(root->right);
  }
}

struct Node* insert(struct Node* node, int key) {
   if (node == NULL) return newNode(key);
   if (key < node->data) { //to the left subtree
      Node *left_child = insert(node->left, key);
      node->left = left_child;
      left_child->parent = node;
   }
   else if (key > node->data) { // to the right subtree
      Node *right_child = insert(node->right, key);
      node->right = right_child;
      right_child->parent = node;
   }
   return node;
}

/* deletion function */

void deleteNode(Node *root, int data)
{
    if(root == NULL){
        cout << "Tree is empty\n";
        return;
    }

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

    while(!q.empty()){
        Node *temp = q.front();
        q.pop();
        if(temp->data == data){
            Node *current = root;
            Node *prev;
            while(current->right != NULL){
                prev = current;
                current = current->right;
            }
            temp->data = current->data;
            prev->right = NULL;
            free(current);
            cout << "Deleted\n";
            return;
        }

        if(temp->left != NULL)
            q.push(temp->left);
        if(temp->right != NULL)
            q.push(temp->right);
    }
 }


int main() {
   struct Node *root = NULL;
   root = insert(root, 100);
   insert(root, 60);
   insert(root, 40);
   insert(root, 80);
   insert(root, 140);
   insert(root, 120);
   insert(root, 160);
   inorderTraverse(root);  cout << endl;
   deleteNode(root, 140);
   deleteNode(root, 60);
   deleteNode(root, 140);
   inorderTraverse(root);  cout << endl;
}
Posted by: Guest on July-01-2021

Browse Popular Code Answers by Language