DSA sheet · Trees · Binary Search Tree pattern

Delete Node in a BST

This video teaches how to remove one value from a binary search tree and still leave a correct BST behind. The teacher splits the job into two stages: first find the node, then delete it. Finding is easy (it's just BST search). Deleting is where the thinking happens, because the node can have 0, 1 or 2 children, and each case needs its own fix. This problem is asked a lot in interviews because it checks whether you really understand the BST rule, and whether you know how recursion can rebuild links on the way back up.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Delete Node (replace with the inorder successor)
• Part B · Homework version (replace with the inorder predecessor)
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

Each node holds a value, a link to its left child and a link to its right child. A missing child is None.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

The BST rule (Binary Search Tree)

A binary search tree is a binary tree where, for every node:

• every value in its left subtree is smaller than the node, and
• every value in its right subtree is bigger than the node.

A subtree means a node together with everything below it. The rule is about all the nodes below, not only the direct children. Look at this tree:

        5
       / \
      3   6
     / \   \
    2   4   7

        5
       / \
      3   6
     / \
    2   8

In the second tree, 8 is a correct right child of 3 (8 > 3). But 8 sits inside the left subtree of 5, and 8 > 5. So the rule breaks at 5. Checking only parent and child is not enough.

On LeetCode the values in a BST are all different (no duplicates), so "smaller" and "bigger" are strict.

Why the BST rule makes searching fast

Standing at a node, you compare the value you want with the node's value. If it is smaller, it can only be on the left; if it is bigger, it can only be on the right. Every step throws away one whole side. So you walk one path from the root downwards, and the work is the height of the tree (the number of levels on the longest path from root to a leaf).

Inorder of a BST is sorted

Inorder traversal means: left subtree, then the node, then the right subtree. In a BST, everything on the left is smaller and everything on the right is bigger, so the node comes out exactly between them. This is true at every node, so the whole output is in increasing order. For the tree above: 2 3 4 5 6 7.

Two words we need from this:

• Inorder successor of a node = the next value after it in that sorted order (the smallest value bigger than it). The successor of 3 is 4.
• Inorder predecessor = the value just before it (the biggest value smaller than it). The predecessor of 3 is 2.

Smallest and largest in a subtree

• Minimum of a BST: start at its root and keep going left until there is no left child. That last node is the smallest. If the root has no left child, the root itself is the minimum.
• Maximum: keep going right until there is no right child.

Part A · Delete Node (replace with the inorder successor)

LeetCode 450

1The question in simple words

You get the root of a BST and a number key. Remove the node whose value is key, and return the root of the tree after the removal. The tree that's left must still be a valid BST. If the key isn't in the tree, return the tree unchanged.

        5
       / \
      3   6
     / \   \
    2   4   7

        5
       / \
      4   6
     /     \
    2       7

        5
       / \
      2   6
       \   \
        4   7

When 3 goes away, its place can be taken by 4 or by 2. Both answers are valid BSTs, and LeetCode accepts either. We will see how to decide.

The teacher points out that "return the root, possibly updated" is a hint: the shape of the tree changes, so links must be re-connected. It can even be the root itself that gets deleted.

2What the constraints tell us

• Number of nodes: 0 to 10⁴ → 0 is allowed. If the tree is empty there is nothing to delete, so return None. That is our first base case.
• n ≤ 10⁴ → an O(n²) idea would be 10⁸ steps. That's right at the edge: it should still pass, but anything above 10⁸ would give TLE (Time Limit Exceeded). We'll do much better anyway: O(height).
• Values and key: −10⁵ to 10⁵ → a normal int is enough. We never add or multiply values here; we only compare and copy them, so overflow can't happen.
• All values are unique → there is at most one node to delete.

3Intuition: find it, then patch the hole

Think of the BST as a family tree where every parent holds a link to each child. Deleting a node is like removing a person from the chart: the hole must be filled so that the parent above is linked to something sensible and the BST order still holds.

1. Stage 1, find. Walk down like a normal BST search: key smaller → go left, key bigger → go right.
2. Stage 2, delete. When you land on the node, look at how many children it has. Each case has a simple patch (below).
3. Re-connect on the way back. The function returns "the new top of this subtree", and the parent stores that answer in its own left or right link.

4Building the conditions from examples

Base case: the root is None

We only have access to the root. The very first check is whether it exists. If it's None (empty tree, or we walked off the bottom because the key isn't there), there is nothing to delete, so return None.

Stage 1: searching with the BST rule

If we get past the base case, the root exists. Now there are exactly three possibilities, the teacher lists them:

• root.val > key → the key can only be in the left subtree. Go left.
• root.val < key → it can only be in the right subtree. Go right.
• otherwise they're equal → this is the node to delete. Don't go further left or right.

In the example (key 3): at 5, is 5 > 3? Yes → go left. At 3, it's not > 3 and not < 3, so it must be equal → found.

Stage 2: the three delete cases

Now we're standing on the node to remove. The teacher asks: how many children does it have?

Case 1: no children (a leaf)

If 3 had no 2 and no 4, removing it leaves nothing behind. Return None, and the parent's link becomes None.

        5
       / \
      3   6
     / \   \
    2   4   7

        5
       / \
      3   6
     / \
    2   4

The call on 7 returns None, so 6 does 6.right = None.

Case 2a: only a left child

If the node has only a left side, that whole left subtree simply moves up one level and takes its place. We don't have to worry about what's inside it: all of it was already smaller than the parent above, so it still fits.

          8
         / \
        3   9
       /
      2
     / \
    1   2.5

          8
         / \
        2   9
       / \
      1   2.5

(2.5 is only there to show a bigger subtree moves up as one block.)

Case 2b: only a right child

Same idea, other side: return the right child, and the parent links to it directly. Even if the right child has its own children, they all come along.

        5
       / \
      3   6
     / \   \
    2   4   7

        5
       / \
      3   7
     / \
    2   4

A neat shortcut: Case 1 is inside Case 2b

In code we don't need a separate leaf check. If root.left is None, return root.right:

• if the right child exists, it moves up (Case 2b) ✓
• if the right child is also None, we return None, which is exactly Case 1 ✓

Then if root.right is None: return root.left. When we reach this line we already know the left child exists (otherwise the line above would have returned), so this is Case 2a.

Case 3: both children exist (the real question)

Back to the main example: delete 3, which has 2 on the left and 4 on the right. Something must sit where 3 was. Which node?

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

          70
        /  |  \
      30   60   80   ← 3 children?!
     /  \
   20   40

70 already has two children (60 and 80). If it moves up, it also has to adopt 30's whole subtree, so it would need three child slots. A binary tree node only has two. We should not move a whole subtree up; we should bring just one suitable value into the empty spot.

Which value can go into the empty spot?

The new value has to be bigger than everything that stays on the left and smaller than everything that stays on the right. Only two values in the tree can do that:

• the largest value in the left subtree (the inorder predecessor), or
• the smallest value in the right subtree (the inorder successor).

The teacher checks this by trying wrong choices. In the 50-tree:

          40
        /    \
      30      70
     /       /  \
   20       60   80

          20
        /    \
      30      70
        \    /  \
        40  60   80

          80
        /    \
      30      70
     /  \    /
   20   40  60

• With 40 on top: everything on the left (20, 30) is smaller, everything on the right is bigger. Valid.
• With 20 on top: 30 and 40 are on its left but bigger than 20. Broken.
• With 80 on top: 60 and 70 are on its right but smaller than 80. Broken.

The same holds for the small example: putting 4 (min of right) or 2 (max of left) in place of 3 both work. Putting anything else would break the rule. So the replacement must be the max of the left subtree or the min of the right subtree. The teacher picks the minimum of the right subtree (the successor). The other choice is your homework (Part B).

How to do the replacement

1. Find the successor: start at root.right and keep going left. For delete-3 that is 4 itself (4 has no left child). For delete-50, start at 70, go left to 60, no more left → 60.
2. Copy its value into the node we're deleting: root.val = successor.val. The node object stays where it is, so its links to the left and right subtrees stay intact. Only the number changes.
3. Now the value exists twice: at the top and down in the right subtree. Remove the lower copy by calling the same function on the right subtree: root.right = self.deleteNode(root.right, successor.val), and store the result, because the right subtree may change shape.

        5
       / \
      3   6
     / \   \
    2   4   7

        5
       / \
      4   6
     / \   \
    2   4   7   ← duplicate

        5
       / \
      4   6
     /     \
    2       7

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

          60
        /    \
      30      70
     /  \       \
   20   40       80

5Approach steps

1. If root is None → return None.
2. If key < root.val → root.left = delete(root.left, key).
3. If key > root.val → root.right = delete(root.right, key).
4. Otherwise this is the node:
   • no left child → return root.right (covers the leaf case too)
   • no right child → return root.left
   • both children → find the min of the right subtree, copy its value into root, then root.right = delete(root.right, that value).
5. Return root.

6Code (Python)

class Solution:
    def deleteNode(self, root, key):
        if root is None:                         # empty / key not found
            return None

        if key < root.val:                       # stage 1: search left
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:                     # stage 1: search right
            root.right = self.deleteNode(root.right, key)
        else:                                    # stage 2: found it
            if root.left is None:                # case 1 and case 2b
                return root.right
            if root.right is None:               # case 2a
                return root.left
            successor = self.minNode(root.right) # case 3
            root.val = successor.val
            root.right = self.deleteNode(root.right, successor.val)
        return root

    def minNode(self, node):
        while node.left is not None:             # keep going left
            node = node.left
        return node

7Code line by line

8Dry run using the call stack

Tree 5, 3, 6, 2, 4, None, 7, key = 3 (the teacher's example).

1. Call delete(5, 3): 3 < 5 → go left, waiting to store the answer in 5.left.
2. Call delete(3, 3): not smaller, not bigger → found. Left (2) exists, right (4) exists → Case 3.
3. minNode(4): 4 has no left child → successor = 4.
4. Copy: the node that held 3 now holds 4. The tree has two 4s for a moment.
5. Call delete(4, 4) on the right subtree (here root.right and the successor are the same node): equal → found. Left is None → return its right, which is None.
6. Back in the old 3-node (now 4): right = None. It returns itself.
7. Back in 5: 5.left = that node (value 4, left child 2, no right child). Return 5.
8. Final tree: 5 → (4 → 2), (6 → 7) ✓ still a BST.

Each call leaves the stack when it returns, and its parent stores the returned node in the right link.

9Complexity & remember

• Time O(h), where h is the height. Finding the node is one walk down. After that, finding the successor and deleting it is another walk down, but only inside the right subtree, continuing below the found node. Together it's still about one root-to-leaf path. The teacher says it as "log n plus log n, which is still log n" for a balanced tree.
• For a balanced BST, h ≈ log n. For a skewed tree (every node has only one child, like a straight line), h = n, so the worst case is O(n).
• Space O(h): the recursive calls waiting on the stack, one per level we went down.

Part B · Homework version (replace with the inorder predecessor)

At the end the teacher leaves a task: solve it again, but fill the hole with the maximum of the left subtree instead. Steps ① to ③ (question, constraints, intuition) are exactly the same as Part A. So are Stage 1 (searching) and Cases 1 and 2. Only Case 3 changes.

4What changes

• Find the predecessor: start at root.left and keep going right until there is no right child.
• Copy its value into root.
• Delete that value from the left subtree: root.left = self.deleteNode(root.left, pred.val).

        5
       / \
      3   6
     / \   \
    2   4   7

        5
       / \
      2   6
       \   \
        4   7

5Approach steps

1. Same as Part A until "both children exist".
2. pred = rightmost node of root.left.
3. root.val = pred.val; root.left = delete(root.left, pred.val).

6Code (Python)

class Solution:
    def deleteNode(self, root, key):
        if root is None:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left
            pred = self.maxNode(root.left)       # max of LEFT subtree
            root.val = pred.val
            root.left = self.deleteNode(root.left, pred.val)
        return root

    def maxNode(self, node):
        while node.right is not None:            # keep going right
            node = node.right
        return node

7Code line by line (only the changed lines)

8Dry run

1. delete(5, 3): 3 < 5 → go left.
2. delete(3, 3): found, both children. maxNode(2): 2 has no right child → pred = 2.
3. Node 3 becomes 2. Call delete(2, 2) on the left subtree: found, no left child → return its right = None.
4. The node (now 2) has left = None, right = 4. 5.left = it. Result: 5 → (2 → _, 4), (6 → 7) ✓

9Complexity

Exactly as Part A: O(h) time, O(h) space. Neither choice is better in general; pick one and be consistent.

Part C · Revision page

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(6, None, TreeNode(7)))
s = Solution()
root = s.deleteNode(root, 3)
print(inorder(root))                 # [2, 4, 5, 6, 7]
print(root.left.val)                 # 4 (successor) or 2 (predecessor version)
root = s.deleteNode(root, 0)         # key not present
print(inorder(root))                 # [2, 4, 5, 6, 7]
print(s.deleteNode(None, 1))         # None

Based on this video: Delete Node in a BST