450. Delete Node in a BST
Problem description:
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
- Search for a node to remove.
- If the node is found, delete the node.
Follow up: Can you solve it with time complexity O(height of tree)
?
Example 1:
1 | Input: root = [5,3,6,2,4,null,7], key = 3 |
Example 2:
1 | Input: root = [5,3,6,2,4,null,7], key = 0 |
Example 3:
1 | Input: root = [], key = 0 |
Constraints:
- The number of nodes in the tree is in the range
[0, 104]
. 105 <= Node.val <= 105
- Each node has a unique value.
root
is a valid binary search tree.105 <= key <= 105
Solution:
Use the BST characteristic
- if
key < root.val
: key on left side - if
key > root.val
: key on right side - if not both cases,
key == root.val
When we find the node we want to delete, we want to find a node to replace root but with minimum reordering. We could use largest node in left subtree OR smallest node in right subtree.
1 | # Definition for a binary tree node. |
time complexity: $O(logn)$
space complexity: $O(1)$
reference:
related problem: