## Interview Questions

### Delete a node from binary search tree

Given root to binary search tree and node "x". Delete "x" from tree.

View Solution

#### Overview

This is relatively simple algorithm that is used to delete node in a tree.

Each time you are deleteing a node you need to consider three possibilities:

- Node has no children - we can safely remove it.
- Node has exactly 1 child - we replace the current node with the child.
- Node has two children - here we need to pick correct node to ensure three will be still BST tree - in this case we need to replace the removed node with three successor.

#### Solution

struct Node
{
int value;
Node *left;
Node *right;
};
Node *tree_delete(Node **root, Node *removeElement)
{
// we look at three cases:
// 1 - no children
// 2 - one child
// 3 - two children (replace with successor)
Node *replacementNode = nullptr;
Node *x = nullptr;
if (removeElement->left == nullptr || removeElement->right == nullptr)
{
// case no children or 1 child
replacementNode = removeElement;
}
else
{
replacementNode = tree_successor(removeElement);
}
if (replacementNode->left != nullptr)
{
x = replacementNode->left;
}
else
{
x = replacementNode->right;
}
if (x != nullptr)
{
x->parent = replacementNode->parent;
}
if (replacementNode->parent == nullptr)
{
*root = replacementNode;
}
else if (replacementNode == replacementNode->parent->left)
{
replacementNode->parent->left = x;
}
else
{
replacementNode->parent->right = x;
}
if (replacementNode != removeElement)
{
removeElement->value = replacementNode->value;
}
return y;
}
Node *tree_successor(Node *node)
{
if (node->right != nullptr)
{
return min_tree_search(node->right);
}
Node *tmpParent = node->parent;
while (tmpParent != nullptr && node = tmpParent->right)
{
tmpParent = node->parent;
}
return tmpParent;
}
Node *min_tree_search(Node *node)
{
while (node->left == nullptr) return node;
return min_tree_search(node->left);
}