Delete a node from Binary Search Tree.cpp

// https://www.youtube.com/watch?v=gcULXE7ViZw
#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *right;
    Node *left;
}

// we are returning root because
// there is a possibility that root node can be deleted.
struct Node * Delete(struct Node *root, int data)
{
    if (root == NULL)
    {
        return root;
    }
    // if the data we are looking for is smaller than root
    // it means it is on the left side.
    else if (data < root->data)
    {
        root->left = Delete(root->left, data);
    }
    else if (data > root->data)
    {
        root->right = Delete(root->right, data);
    }
    // Wohoo! I found you, I will delete you!
    else
    {
        // Case 1: No child
        if (root->left == NULL && root->right == NULL)
        {
            delete root;
            root = NULL;
        }
        // Case 2: One child
        // then we take right one (because it is bigger)
        // then put it as new root
        else if (root->left == NULL)
        {
            struct Node *temp = root;
            root = root->right;
            delete temp;
        }
        else if (root->right == NULL)
        {
            struct Node *temp = root;
            root = root->left;
            delete temp;
        }
        // Case 3: 2 children
        else
        {
            // find minimum at right
            struct Node *temp = FindMin(root->right);
            root->data = temp->data;
            root->right = Delete(root->right, temp->data);
        }
    }
    return root;
}

struct Node *FindMin(Node *root, int data)
{
    Node *currentNode = root;
    while (data->left != NULL)
    {
        currentNode = data->left;
    }
    return currentNode;
}