Traversal

Delete Node in a BST

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.

public TreeNode DeleteNode(TreeNode root, int key)
{
        
    if(root == null) return root;
    if(key<root.val)
    {
        root.left = DeleteNode(root.left, key);     
    }
    else if(key>root.val)
    {
        root.right = DeleteNode(root.right, key);
    }
    else
    {
        if(root.left == null) return root.right;
        if(root.right == null) return root.left;
        
        var rightSmallest = root.right;
        while(rightSmallest.left != null) rightSmallest = rightSmallest.left;
        rightSmallest.left = root.left;
        return root.right;
    }
    
    return root;
}