DSA Tracker

Visualize

Delete Node in a BST

Standard Hibbard deletion: splice out, or replace with the inorder successor

time O(h)space O(h) recursion stack

Finding the node to delete is ordinary BST search. The real problem is filling the hole it leaves behind: a leaf can simply vanish, a node with one child promotes that child into its own spot, but a node with two children cannot just disappear without breaking the ordering — instead its value is overwritten by its inorder successor (the smallest value in its right subtree), and that successor's original node is then deleted from further down, where it is guaranteed to have at most one child.

Details

Animated on: root = [5, 3, 6, 2, 4, null, 7], key = 3 — delete the node holding 3 and return the updated BST. Expected answer: [5, 4, 6, 2, null, null, 7].

Problem:Delete Node in a BSTMedium

Pattern:Binary Search Tree Problems

Standard Hibbard deletion: splice out, or replace with the inorder successor

step 1 / 14

2
3
4
5
6
7

Call stack

deleteNode(5, key=3)

Call deleteNode(5, key=3). Node 5 is not null, so compare it against the key.

Pseudocode
1FUNCTION deleteNode(node, key):
2  IF node = null: RETURN null
3  IF key < node.val: node.left <- deleteNode(node.left, key)
4  ELSE IF key > node.val: node.right <- deleteNode(node.right, key)
5  ELSE:
6    IF node.left = null: RETURN node.right
7    IF node.right = null: RETURN node.left
8    succ <- MIN(node.right)
9    node.val <- succ.val
10    node.right <- deleteNode(node.right, succ.val)
11  RETURN node

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Call deleteNode(5, key=3). Node 5 is not null, so compare it against the key.
  2. 3 < 5: the key can only live in the left subtree, so recurse into node.left (3).
  3. Call deleteNode(3, key=3). Node 3 is not null, so compare it against the key.
  4. 3 equals 3 — this is the node to remove. How we splice it out depends on how many children it has.
  5. 3 has BOTH children (2 and 4) — the hard case. It cannot simply be dropped without breaking the ordering, so it is replaced by its inorder successor instead.
  6. succ <- MIN(node.right): walk left from 4 as far as possible. 4 has no left child, so the inorder successor is 4 — the smallest value greater than 3.
  7. node.val <- succ.val: this node keeps its position in the tree (still here) but now stores 4. The old value 3 still exists once, further down, and must be removed.
  8. node.right <- deleteNode(node.right, 4): recurse into the right subtree to delete the ORIGINAL 4 node — the value that got copied up.
  9. Call deleteNode(4, key=4). Node 4 is not null, so compare it against the key.
  10. 4 equals 4 — this is the node to remove. How we splice it out depends on how many children it has.
  11. 4 has no left child, so it is spliced out by returning node.right (null) straight to the caller.
  12. RETURN node: this frame hands 4 back up unchanged in identity, now with its subtree links updated.
  13. Back at 5: node.left is reattached to whatever deleteNode returned for that subtree.
  14. RETURN node: this frame hands 5 back up unchanged in identity, now with its subtree links updated.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Delete Node in a BST in the editorAll BST problemsBack to roadmap