FULL BINARY TREEE AND BINARY SEARCH TREE

/////////////////*************DELETION IN BST ***********/////////////////

///////// 3 CASES ////////////

/////// 0 CHILD = delete that node and  directlty return null


/////// 1 CHILD 
/// store the child one in temp and than delete the node and add temp one in bst 

////////2 children 
///  replace the favourable node with highest value in left child and than delete the favourable node frm tree.....
#include <iostream>
#include <queue>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int d) {
        this->data = d;
        this->left = NULL;
        this->right = NULL;
    }
};

Node* insertIntoBST(Node* root, int d) {
    // base case 
    if (root == NULL) {
        root = new Node(d); // Create a new node
        return root; // Return the newly created node
    }
    if (d > root->data) {
        // Insert in the right subtree
        root->right = insertIntoBST(root->right, d);
    } else {
        // Insert in the left subtree
        root->left = insertIntoBST(root->left, d);
    }
    return root; // Return the root of the subtree
}

void levelOrderTraversal(Node* root) {
    if (root == NULL) 
        return; // If the tree is empty, return

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

    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        cout << temp->data << " "; // Print the current node's data

        // Push left and right children into the queue
        if (temp->left) {
            q.push(temp->left);
        }
        if (temp->right) {
            q.push(temp->right);
        }
    }
    cout << endl; // Print a new line after level order traversal
}

void takeInput(Node*& root) {
    int data;
    cin >> data;

    while (data != -1) {
        root = insertIntoBST(root, data); // Update the root pointer
        
        // Print the current state of the BST after each insertion
        cout << "Current state of the BST after inserting " << data << ": ";
        levelOrderTraversal(root);
        
        cin >> data;
    }
}

void inorder(Node* root) {
    // base case
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

void preorder(Node* root) {
    // base case
    if (root == NULL) {
        return;
    }
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

void postorder(Node* root) {
    // base case
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Node* minVal(Node* root) {
    Node* temp = root;
    
    while (temp->left != NULL) {
        temp = temp->left;
    }
    return temp;
}

Node* maxVal(Node* root) {
    Node* temp = root;
    
    while (temp->right != NULL) {
        temp = temp->right;
    }
    return temp;
}
Node* deleteFromBST(Node* root ,int val){
    // base case
    if(root == NULL){
        return root;
    }
    if(root->data == val){
        // 0 child
        if(root->left == NULL && root->right == NULL){
            delete root;
            return NULL;
            // here we directly deleting the root we want 
        }
        // 1 child
        if(root->left != NULL && root->right == NULL){
            Node* temp = root->left;
            delete root;
            return temp;
            // here we delete that root and save the children keyt into temp variable 
        }
        if(root->left == NULL && root->right != NULL){
            Node* temp = root->right;
            delete root;
            return temp;
        }
        // 2 children
        if(root->left != NULL && root->right != NULL ){
            int mini = minVal(root->right) -> data;
            root-> data = mini;
            root-> right = deleteFromBST(root->right,mini);
            return root;
            // here we take minimum from the rightleftsubtree or maximum from the leftsubtree  and copy the value of that value we taken above(MIN) and now delete that MIN value and than delete the root one which one we want tor delete  
        }
    }
    else if (root-> data > val){
        //left part me ajaio
        root->left = deleteFromBST(root->left,val);
        return root;
    }
    else{
        //right part me ajaio
        root->right = deleteFromBST(root->right,val);
        return root;
    }
}

int main() {
    Node* root = NULL;
    cout << "Enter the data for BST (end with -1): ";
    takeInput(root);
    
    cout << "printing inorder" << endl;
    inorder(root);
    
    cout << endl << "printing preorder" << endl;
    preorder(root);
    
    cout << endl << "printing postorder" << endl;
    postorder(root);
    
    cout << endl << "min value is " << minVal(root)->data << endl;
    cout << "max value is " << maxVal(root)->data << endl;
    
    cout << endl << "before deletion" << endl;
    inorder(root);
    // Corrected deletion part
    root = deleteFromBST(root, 30); // Update the root with the new tree structure after deletion
    
    cout << endl << "after deletion" << endl;
    inorder(root); // Print inorder traversal to confirm deletion
   
    
    return 0;
}