Problem editorial

Delete Node in a BST

MediumTree Traversal Patterns (DFS & BFS)Binary Search TreeBinary TreeTree

Delete Node in a BST: the approach in brief

The problem

Given root, the root of a binary search tree, and key, remove the node whose value equals key and return the root of the resulting tree. A binary search tree is a binary tree where every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.

Pattern

Delete Node in a BST is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Inorder Traversal subpattern. The pattern covers preorder, inorder, level order traversal, LCA, and serialization

Approach outline

Use the ordering property of a binary search tree to decide whether to continue into the left or right subtree.
When the target has at most one child, its replacement is immediate: the child, or null if there is no child.
For a target with two children, choose either the next larger value or the next smaller value, copy it into the target, and delete that replacement from its original position.

Complexity

The reference solution runs in O(h), where h is the height of the tree; O(n) in the worst case. time and O(h) for recursive call stack; O(n) in the worst case. space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Delete Node in a BST and the problems around it

Delete Node in a BST is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Inorder Traversal subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Delete Node in a BST