In the previous post we looked at finding the $$k^{th}$$ smallest node in a binary search tree. In this post we are going to look at removing a node from a binary search tree.

## Code

If the node to be deleted is a leaf node then we just simply delete it. If the node has one child then we replace the node with the child and remove the child. However, it gets a bit tricky when the node has two children. If a node has two children we replace it with its in-order successor and remove the successor. This will be the smallest node in the right subtree of the node. Time complexity for this algorithm is $$O(h)$$ where $$h$$ is the height of the tree. Here’s the code:

public TreeNode<T> Delete(T value)
{
return RemoveNode(_root, value);
}

private TreeNode<T> RemoveNode(TreeNode<T> node, T value)
{
if (node is null)
{
return null;
}

if (node.Value.CompareTo(value) > 0)
{
node.Left = RemoveNode(node.Left, value);
return node;
}

if (node.Value.CompareTo(value) < 0)
{
node.Right = RemoveNode(node.Right, value);
return node;
}

if (node.Left is null)
{
return node.Right;
}

if (node.Right is null)
{
return node.Left;
}

var parent = node;
var successor = node.Right;

while(successor.Left != null)
{
parent = successor;
successor = successor.Left;
}

if (parent != node)
{
parent.Left = successor.Right;
}
else
{
parent.Right = successor.Right;
}

node.Value = successor.Value;
return node;
}


In this post we spoke about how to remove a node from a binary search tree. All the code is available on GitHub. In the next post we are going to look at another LeetCode problem where we create a balanced binary search tree from a sorted array. Till next time, thanks so much for reading.

Tags:

Updated: