[leetcode #450] Delete Node in a BST

Problem

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.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Constraints:

・ The number of nodes in the tree is in the range [0, 10⁴].
・ -10⁵ <= Node.val <= 10⁵
・ Each node has a unique value.
・ root is a valid binary search tree.
・ -10⁵ <= key <= 10⁵

Follow up: Could you solve it with time complexity O(height of tree)?

Idea

한참을 풀려고 시도했는데 계속 틀려서 포기했다. 요새 머리가 안 돌아가는게 느껴져 슬프다... 🥲

기본적인 알고리즘은 생각하기 쉽다.

주어진 key값이 현재 노드보다 크면 오른쪽 subtree를 탐색하고, 작으면 왼쪽 subtree를 탐색한다. 이 때 조건에 따라 자식노드를 재귀함수가 리턴하는 노드로 설정해준다.

위와 같은 조건으로 탐색을 계속했음에도 일치하는 값을 가진 노드가 나오지 않을 경우 재귀함수에서 null을 리턴시켜 탐색을 종료한다.

key와 같은 값을 가진 노드가 나올 경우, 왼쪽 자식 노드가 null이면 오른쪽 자식 노드를, 오른쪽 자식 노드가 null이면 왼쪽 자식 노드를 리턴한다. 자식 노드를 모두 가질 경우, 오른쪽 subtree에서 가장 작은 값을 찾는다. BST기 때문에 tree의 가장 왼쪽에 위치한 노드가 최소값이 된다.

key와 같은 값을 가진 노드를 위 단계에서 찾은 최소값으로 설정해주고, 오른쪽 자식 노드와 최소값을 인자로 하여 deleteNode 재귀함수를 호출해준다. 처음 tree 대신 subtree를 풀기 위해 재귀함수를 호출하는 것이다.

보기에는 간단해 보이지만 노드의 값을 바꿔주는 게 생각이 도무지 나지 않았다. 노드 값을 바꾸지 않고 노드를 통째로 바꾸려고 하니 if-else 문으로 뒤범벅된 코드가 만들어졌던 것이다.

오늘 리트코드 문제는 Medium인데도 못 풀었다는 사실이 너무 짜증이 나 잠을 못 잘 듯 하다 😅

Solution

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {

        if (root == null) return null; 

        if (root.val < key)
            root.right = deleteNode(root.right, key);
        else if (root.val > key)
            root.left = deleteNode(root.left,key);

        else{
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;

            TreeNode minNode = minNext(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, root.val);
        }

        return root;
    }

    private TreeNode minNext(TreeNode node) {
        while (node.left != null) node = node.left;
        return node;
    }
}

Reference

https://leetcode.com/problems/delete-node-in-a-bst/