Return to Question

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1.Search for a node to remove.
2.If the node is found, delete the node.

Problem Statement

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

I tried to solve deleting node in BST problem, but unfortunately my solution's inefficient, compared to other results (some of them with recursion). Please, help me to improve it

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1.Search for a node to remove.
2.If the node is found, delete the node.

Here is my solution (unfortunately inefficient)

I tried to solve leetcode problem for deleting node in BST, but unfortunately my solution's inefficient, compared to other results (some of them with recursion). Please, help me to improve it

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    struct TreeNode *parrent = NULL, *cur = root;
    while (cur && cur->val != key) {
        parrent = cur;
        if (key < cur->val)
            cur = cur->left;
        else
            cur = cur->right;
    }
    if (!cur)
        return root;
    if (!cur->left) {
        if (!parrent)
            root = root->right;
        else if (parrent->left == cur)
            parrent->left = cur->right;
        else
            parrent->right = cur->right;
    } else if (!cur->right) {
        if (!parrent)
            root = root->left;
        else if (parrent->left == cur)
            parrent->left = cur->left;
        else
            parrent->right = cur->left;
    } else {
        struct TreeNode *tmp = cur->left;
        while (tmp->right) {
            tmp = tmp->right;
        }
        tmp->right = cur->right;
        if (!parrent) {
            root = root->left;
        }
        else if (parrent->left == cur)
            parrent->left = cur->left;
        else
            parrent->right = cur->left;
    }
    free(cur);
    return root;
}

I tried to solve deleting node in BST problem, but unfortunately my solution's inefficient, compared to other results (some of them with recursion). Please, help me to improve it

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    struct TreeNode *parrent = NULL, *cur = root;
    while (cur && cur->val != key) {
        parrent = cur;
        if (key < cur->val)
            cur = cur->left;
        else
            cur = cur->right;
    }
    if (!cur)
        return root;
    if (!cur->left) {
        if (!parrent)
            root = root->right;
        else if (parrent->left == cur)
            parrent->left = cur->right;
        else
            parrent->right = cur->right;
    } else if (!cur->right) {
        if (!parrent)
            root = root->left;
        else if (parrent->left == cur)
            parrent->left = cur->left;
        else
            parrent->right = cur->left;
    } else {
        struct TreeNode *tmp = cur->left;
        while (tmp->right) {
            tmp = tmp->right;
        }
        tmp->right = cur->right;
        if (!parrent) {
            root = root->left;
        }
        else if (parrent->left == cur)
            parrent->left = cur->left;
        else
            parrent->right = cur->left;
    }
    free(cur);
    return root;
}