/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* deleteNode(struct TreeNode* root, int key){

    if(root == NULL)
    {
        //checks if this node is a leaf
        return root;
    }else if(root->val == key)
    {

        if(root->right == NULL && root->left == NULL)
        {
            //if the to-be deleted node is a leaf
            //assign it to NULL
            root = NULL;
        }else
        {
            //the problem lies in shifitng the nodes under the deleted one (subtree) up the tree
            //And not assigning it to null
            if(root->right->left != NULL && root->left->right == NULL)
            {
                if(root->right == NULL)
                    root->val = root->left->val;
                else if(root->left == NULL)
                    root->val == root->right->val;
                else
                    root->val = NULL;
            }else if(root->right->left != NULL)
            {
                root->val = root->right->left->val;
                root = deleteNode(root->right->left, root->val);
            }else if(root->right->left != NULL)
            {
                root->val = root->left->right->val;
                root = deleteNode(root->left->right, root->val);
            }else
            {
                root->val = NULL;
            }

        }
        return root;
    }
    else
    {
        //recursive traversal
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }

}