Delete a node in binary tree

Question

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.

Here is my solution (unfortunately inefficient)

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;
}

Answer 1

You could save on usage of struct by a typedef.

typedef struct TreeNode {} Tree;

First two different prototypes are thinkable.

Input parameter overwriting returned result.

struct TreeNode* deleteNode(struct TreeNode* node, int key);
struct TreeNode* tree = NULL; // root
...
tree = deleteNode(tree, 8);

Input output parameter overwriting the parameter.

void deleteNode(struct TreeNode** node, int key);
struct TreeNode* tree = NULL; // root
...
deleteNode(&tree, 8);

The second form is shorter, hence I mention it. But for instance the language Java does not allow to alter passed input variables.

The trick for such node juggling is to start with a recursive algorithm: do the simple case, and let a clone call again do the rest.

For clarity I keep the returns as soon as possible - the code can written shorter.

struct TreeNode* deleteNode(struct TreeNode* node, int key) {
    if (!node) {
        return NULL;
    }
    if (key < node->val) {
        node->left = deleteNode(node->left, key); 
        return node;
    }
    if (key > node->val) {
        node->right = deleteNode(node->right, key); 
        return node;
    }
    // key == node->val
    struct TreeNode* result;
    if (!node->left) {
        result = node->right;
    } else if (!node->right) {
        result = node->left;
    } else {
        struct TreeNode** adjacentLeaf = &(node->left);
        while ((*adjacentLeaf)->right) {
            adjacentLeaf = &(*adjacentLeaf)->right;
        }
        // Rotate the pointers:
        result = *adjacentLeaf;
        (*adjacentLeaf)->right = node->right;
        (*adjacentLeaf)->left = node->left;
        *adjacentLeaf = (*adjacentLeaf)->left;
    }
    free(node);
    return result;
}

This does a pointer rotation (7, 6, 3):

      node  &7        =>    result   &6
            / \                      / \
           1   8                    1   8
            \                        \
             \                        \
              3                        3
     adjLeaf   \.right                  \
                &6                       5
                / _
               5

I have used a pointer to a pointer, an alias, a pointer to a field (left or right), so that the field may be modified.

There is also a variant where not the nodes a changed but the field values overwritten.

And of course one could rotate pointers not with the left max leaf, but with the right min leaf.

Personally I find the void deleteNode(struct TreeNode** node, int key) version a bit easier to grasp.

I did not run this code through a compiler.

Answer 2

Reflection of Requirements

The description says "the deletion can be divided into two stages". However, that isn't reflected in the code. I believe it would gain readability from this division, be it by a comment line above and an empty one in between or even from using separate function. Putting code for locating a node into a separate function can come useful in other places, too, but that's just a side note and not relevant to your assignment.

No Recursion

You're not using recursion and that will complicate this a lot. Think about looking at a node and considering whether it's the one to remove. You compare the key field and, depending on whether it's equal, less or greater, you know whether to delete this very node, delete the node from the left subtree or the right subtree.

The ininitial part of the function then looks like this:

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        ...
    }
}

If you look closely, you will find that this doesn't check for null pointers. You can do that before recursing, but you could also do an initial check of root. That way, you can use a null pointer to represent an empty BST, which is probably consistent.

Documentation

What is your strategy when the node to delete has both a left and right subtree? This is the most complicated part in this code, but there is zero explanation on the code. Without diving deeper into it, I couldn't tell if it's correct or not, so at least I would advise a good set of unit tests that exercise all corner cases.

Also, and that's why I mention that specifically, the used strategy affects how the tree looks like afterwards, in particular how balanced it is. That in turn affects how quickly other operations on that tree run and whether perhaps that exceeds some time limits. Just to illustrate, a badly balanced tree performs like a linked list, so deleting a node turns from an O(log n) to an O(n) operation.

Nitpicks

• parrent is a typo, you mean parent.
• If the node is not found, this does nothing. If multiple such nodes are found, only one of them is removed, or? This isn't your fault but that of the assignment, but not being able to tell the difference might cause brittle code down the line when this is used.