What is the core idea behind Delete Node in a BST?

The core idea is to use BST search to locate the target, then reconnect the subtree based on how many children that node has. Zero children means remove it, one child means promote that child, and two children usually means copy in the inorder successor and then delete that successor from the right subtree.

Why does replacing with the inorder successor work in Delete Node in a BST?

The inorder successor is the smallest value in the target node's right subtree, so it is larger than everything on the left and no larger than the remaining values on the right. That makes it a safe replacement that preserves BST ordering after the original node's value is overwritten.

Can I use the inorder predecessor instead of the successor?

Yes. The predecessor, which is the largest value in the left subtree, is equally valid. The choice usually comes down to implementation preference, but you must consistently remove the moved value from the subtree it came from.

What pattern is this problem testing?

This problem tests binary-tree traversal and state tracking under BST constraints. You are not just visiting nodes; you are returning updated subtree roots after structural changes, which is the state-management detail that interviewers usually focus on.

What happens if the key is not present in the tree?

You simply return the original BST unchanged. A clean solution keeps descending left or right until it hits null, then bubbles the unchanged subtree roots back up without modifying any links.

#450

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key ，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：首先找到需要删除的节点；如果找到了，删除它。示例 1: 输入： root = [5,3…

树二叉搜索树二叉树

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
节点值唯一
root 是合法的二叉搜索树
-10⁵ <= key <= 10⁵

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

lightbulb

解题思路

方法一：递归

二叉搜索树有以下性质：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉搜索树。

我们可以递归判断当前节点 $root$ 与 $key$ 的大小关系：

若 $root.val>key$ ，则递归左子树；
若 $root.val<key$ ，则递归右子树；
若 $root.val=key$ $r oo t . v a l = k ey$ ，则进一步判断：
1. 若 $root$ 没有左子树，则 $root.right$ 顶替 $root$ 的位置；
2. 若 $root$ 没有右子树，则 $root.left$ 顶替 $root$ 的位置；
3. 若 $root$ 同时存在左右子树，则将左子树转移至右子树的最左节点的左子树上，然后 $root.right$ 顶替 $root$ 的位置。

时间复杂度 $O(H)$ ，其中 $H$ 是树的高度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
            return root
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
            return root
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        node = root.right
        while node.left:
            node = node.left
        node.left = root.left
        root = root.right
        return root

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want to see whether you separate the search phase from the subtree-rewiring phase instead of mixing cases too early.
question_mark
They are checking whether you know why the inorder successor or predecessor preserves BST order for the two-child delete case.
question_mark
They care about whether your function returns the new subtree root correctly, especially when deleting the original root node.

warning

常见陷阱

外企场景

error
Replacing a two-child node's value with its successor but forgetting to delete the successor node, which leaves a duplicate in the BST.
error
Updating the child pointer locally but not returning it upward, causing the parent link or root replacement to stay stale.
error
Using a generic binary-tree delete idea that ignores BST ordering and accidentally breaks the in-order sorted property.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use the inorder predecessor from the left subtree instead of the successor from the right subtree for the two-child case.
arrow_right_alt
Write the deletion iteratively by tracking the parent pointer, which removes recursion but makes edge handling around the root more manual.
arrow_right_alt
Augment the BST with parent pointers or subtree metadata, where deletion still follows the same cases but requires extra state updates after relinking.

help

常见问题

外企场景

继续练习

#449 序列化和反序列化二叉搜索树 #501 二叉搜索树中的众数 #530 二叉搜索树的最小绝对差