Delete in a BST

Table of Contents +

Adding a node to a Binary Search Tree feels easy. You find an empty spot and drop the value in. But deleting a node is the part that trips up a lot of students. Here is the problem. When you pull a node out, you leave a hole. And the tree still has to stay a valid BST after that. So the real question is not “how do I remove it”. It is “what do I put back in its place”.

In this tutorial we will delete from a BST one case at a time. Take it slow. Each case is simple on its own.

🌳 A Quick Refresher

A Binary Search Tree is a tree where, for every node, all the smaller values sit on its left and all the larger values sit on its right. That one rule is what makes search fast. When we delete a node, we have to keep that rule true.

Here is the tree we will work with for the whole tutorial.

So 50 is at the top. Everything smaller than 50 is on the left. Everything larger is on the right. The same rule holds at every node below too.

🧩 The Three Cases of Deletion

When you delete a node, the work depends on how many children that node has. There are three cases, and that is the whole idea behind delete. Let us name them first. Then we will look at each one.

The node is a leaf. It has no children.
The node has one child. Only a left child, or only a right child.
The node has two children. Both a left and a right child.

The first two are short. The third one is where the real thinking happens. Let us walk through them.

🍃 Case 1: The Node Is a Leaf

A leaf is a node with no children. This is the easiest case. You just remove it. Nothing else hangs off it, so nothing breaks.

Say we delete 20 from our tree. 20 is a leaf. We cut it off and we are done.

See? 30 just loses its left child. The rest of the tree does not care. The leaf goes away and the BST rule still holds.

🌿 Case 2: The Node Has One Child

Now say the node has exactly one child. We cannot just delete it. If we did, that child and everything below it would be lost. So instead we link the child straight to the parent. The child takes the deleted node’s place.

Imagine our tree had 70 with only a right child, 80. If we delete 70, then 80 moves up and connects directly to 50.

The idea is simple. The deleted node was a bridge between its parent and its child. We remove the bridge and join the two ends. Because of the BST rule, the single child fits perfectly in the freed spot.

🔁 Case 3: The Node Has Two Children

This is the interesting one. The node has a left child and a right child. We cannot just move one child up. If we did, the other child would have nowhere to go.

So here is the trick. We do not really delete the node’s spot. We keep the spot and put a different value in it. Which value? The one that keeps the BST rule true. That value is the inorder successor. It is the smallest value in the node’s right subtree.

Why the smallest on the right? Think about it. That value is bigger than everything on the left. And it is smaller than everything else on the right. So it slots right in without breaking anything.

Let us delete 50, the root. Its right subtree holds 70, 60, and 80. The smallest there is 60. So we copy 60 up into the root’s spot. Then we go delete the old 60. The old 60 is now a leaf, so that part is easy.

So 60 took 50’s place. The original 60 node is gone. And the tree is still a valid BST. Read it left to right and the numbers still come out in order.

Tip

To find the inorder successor, go once into the right child. Then keep going left until you cannot go left anymore. That last node holds the smallest value in the right subtree.

📋 Steps to Delete a Node

Here is the full plan as one set of steps. Every deletion follows this.

Start at the root and search for the value to delete, the same way you search a BST. Go left if the value is smaller, right if it is larger.
If the value is not in the tree, do nothing and return.
When you find the node, check how many children it has.
If it is a leaf, remove it and return nothing in its place.
If it has one child, return that child to take its place.
If it has two children, find the inorder successor, which is the smallest in the right subtree. Copy the successor’s value into the current node. Then delete the successor from the right subtree.

Notice that case 3 turns into case 1 or case 2. After we copy the successor up, we still have to delete the successor. And a successor never has a left child. So it is always a leaf or a one-child node. Neat, right?

💻 Delete in 5 Languages

Now the code. We build the same small tree. We print its values in sorted order using an inorder traversal. We delete a node. Then we print again so you can see the change. An inorder traversal of a BST always gives you the values in sorted order, so it is a clean way to check the tree is still valid.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Insert a value into the BST and return the (possibly new) root
def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

# Find the node with the smallest value (left-most node)
def find_min(node):
    while node.left is not None:
        node = node.left
    return node

# Delete a value and return the new root of this subtree
def delete_node(root, value):
    if root is None:
        return None                         # value not found

    if value < root.value:
        root.left = delete_node(root.left, value)
    elif value > root.value:
        root.right = delete_node(root.right, value)
    else:
        # Found the node to delete
        if root.left is None:               # leaf or only right child
            return root.right
        if root.right is None:              # only left child
            return root.left
        # Two children: get inorder successor, then delete it
        successor = find_min(root.right)
        root.value = successor.value
        root.right = delete_node(root.right, successor.value)
    return root

# Print values in sorted order (inorder traversal)
def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.value, end=" ")
    inorder(root.right)

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

print("Before delete:", end=" ")
inorder(root)
print()

root = delete_node(root, 50)  # delete the root (two children)

print("After delete 50:", end=" ")
inorder(root)
print()

The output of the above code will be:

Before delete: 20 30 40 50 60 70 80
After delete 50: 20 30 40 60 70 80

Look at the output. Before deleting, the values come out as 20 30 40 50 60 70 80, which is sorted. After deleting 50, we get 20 30 40 60 70 80. Still sorted, just missing the 50. That sorted order is our proof that the tree is still a valid BST.

Note

We wrote deleteNode to return the new root of the subtree it works on. The caller saves it back with root.left = deleteNode(...). This return-and-reassign style is what lets one child quietly move up into the parent’s link. It keeps the code short and saves us from tracking the parent by hand.

⏱️ Time and Space Complexity

The cost of deleting comes mostly from finding the node first. You walk down the tree. On a balanced BST the height is about O(log n). The successor search and the relinking are cheap on top of that.

Tip

On a balanced BST, delete runs in O(log n) on average. The work follows the height of the tree, and a balanced tree has a height of about log n.

Here is the full picture, including the worst case. The worst case happens when the tree is skewed. A skewed tree looks like a straight line instead of a bushy tree. Then the height becomes O(n).

Case	Time	Space
Average (balanced tree)	O(log n)	O(log n)
Worst (skewed tree)	O(n)	O(n)

The space is O(log n) on average because the recursion goes as deep as the height of the tree. On a skewed tree that depth becomes O(n).

⚠️ Common Mistakes

A few things trip students up here. Watch for these.

Forgetting the “not found” case. If the value is not in the tree, your code must just return without changing anything.
Mixing up successor and predecessor. The inorder successor is the smallest in the right subtree. Some people grab the largest in the left subtree instead, which is the predecessor. Both work, but pick one and stay consistent.
Copying the successor’s value but forgetting to delete the old successor node. Then the same value sits in two places.
Not reassigning the returned subtree. If you call deleteNode but throw away what it returns, the link never updates and your change is lost.

🧩 What You’ve Learned

✅ Deleting from a BST has three cases based on how many children the node has.

✅ A leaf is removed directly, and a node with one child is replaced by that child.

✅ A node with two children is replaced by its inorder successor, the smallest value in its right subtree.

✅ The two-children case always turns into a leaf or one-child delete, so the hard case reuses the easy ones.

✅ An inorder traversal staying sorted is your proof the tree is still a valid BST.

✅ Delete runs in O(log n) on average on a balanced tree and O(n) in the worst case on a skewed tree.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Insert in a BST
Validate Binary Search Tree

Previous Insert in a BST Next Introduction to Heap

Share & Connect

Share on LinkedIn