450 Delete Node in a BST

450. Delete Node in a BST​
1. Question
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:
1.Search for a node to remove.
2.If the node is found, delete the node.
Note:Time complexity should be O(height of tree).
Example:
1
root = [5,3,6,2,4,null,7]
2
key = 3
3
​
4
    5
5
   / \
6
  3   6
7
 / \   \
8
2   4   7
9
​
10
Given key to delete is 3. So we find the node with value 3 and delete it.
11
​
12
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
13
​
14
    5
15
   / \
16
  4   6
17
 /     \
18
2       7
19
​
20
Another valid answer is [5,2,6,null,4,null,7].
21
​
22
    5
23
   / \
24
  2   6
25
   \   \
26
    4   7
Copied!
2. Implementation
(1) Iteration
1
class Solution {
2
    public TreeNode deleteNode(TreeNode root, int key) {
3
        TreeNode preNode = null, curNode = root;
4
​
5
        while (curNode != null && curNode.val != key) {
6
            preNode = curNode;
7
            if (curNode.val < key) {
8
                curNode = curNode.right;
9
            }
10
            else{
11
                curNode = curNode.left;
12
            }
13
        }
14
​
15
        if (preNode == null) {
16
            return getSuccessor(curNode);
17
        }
18
        else if (preNode.left == curNode) {
19
            preNode.left = getSuccessor(curNode);
20
        }
21
        else if (preNode.right == curNode) {
22
            preNode.right = getSuccessor(curNode);
23
        }
24
        return root;
25
    }
26
​
27
    public TreeNode getSuccessor(TreeNode node) {
28
        if (node == null) {
29
            return null;
30
        }
31
​
32
        if (node.left == null) {
33
            return node.right;
34
        }
35
​
36
        if (node.right == null) {
37
            return node.left;
38
        }
39
​
40
        TreeNode preNode = null, successor = node.right;
41
​
42
        while (successor.left != null) {
43
            preNode = successor;
44
            successor = successor.left;
45
        }
46
​
47
        successor.left = node.left;
48
        if (node.right != successor) {
49
            preNode.left = successor.right;
50
            successor.right = node.right;
51
        }
52
        return successor;
53
    }
54
}
Copied!
（2) Recursion
1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode(int x) { val = x; }
8
 * }
9
 */
10
class Solution {
11
    public TreeNode deleteNode(TreeNode root, int key) {
12
        if (root == null) {
13
            return null;
14
        }
15
​
16
        if (root.val < key) {
17
            root.right = deleteNode(root.right, key);
18
        }
19
        else if (root.val > key) {
20
            root.left = deleteNode(root.left, key);
21
        }
22
        else {
23
            if (root.left == null) {
24
                return root.right;
25
            }
26
​
27
            if (root.right == null) {
28
                return root.left;
29
            }
30
​
31
            TreeNode successor = getInorderSuccessor(root.right);
32
            // 注意这一步是改变了原来的数据，面试时不一定被允许
33
            root.val = successor.val;
34
            root.right = deleteNode(root.right, root.val);
35
        }
36
        return root;
37
    }
38
​
39
    public TreeNode getInorderSuccessor(TreeNode node) {
40
        while (node.left != null) {
41
            node = node.left;
42
        }
43
        return node;
44
    }
45
}
Copied!
3. Time & Space Complexity
Iteration:时间复杂度O(h), 空间复杂度O(1)
Recursion: 时间复杂度O(h), 空间复杂度O(h)

222 Count Complete Tree Nodes

156 Binary Tree Upside Down

Last modified 2yr ago

Copy link

Contents

450. Delete Node in a BST

1. Question

2. Implementation

3. Time & Space Complexity

450. Delete Node in a BST​

1. Question

2. Implementation

3. Time & Space Complexity

450. Delete Node in a BST