Pattern visualizer

Delete Node in BST

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. 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]..

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

time O(h)space O(h) recursion stackstep 1 / 14

Call stack

deleteNode(5, key=3)

line 2

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

Where to practice BST

Practice BST problems All BST problems Back to roadmap