Binary Search Tree in Action (Basic Operations)

In our previous article, The Essence of Binary Search Tree (Features), we introduced the basic features of a Binary Search Tree (BST). We also used the "inorder traversal is sorted" characteristic of BSTs to solve several problems. This article will implement basic BST operations: verifying the legality of a BST, and performing insertions, deletions, and searches. Among these, "deletion" and "verifying legality" are slightly more complex.

The basic operations of a BST mainly rely on the "left is smaller, right is larger" property, allowing for binary search-like operations within a binary tree, thus making element search very efficient. For example, the following is a valid binary tree:

For problems related to BST, you might often see code logic similar to the following:

void BST(TreeNode root, int target) {
    if (root.val == target)
        // found the target, do something
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

void BST(TreeNode* root, int target) {
    if (root->val == target)
        // found the target, do something
    if (root->val < target) 
        BST(root->right, target);
    if (root->val > target)
        BST(root->left, target);
}

def BST(root: TreeNode, target: int) -> None:
    if root.val == target:
        # target found, do something
    if root.val < target:
        BST(root.right, target)
    if root.val > target:
        BST(root.left, target)

func BST(root *TreeNode, target int) {
    if root.Val == target {
        // found the target, do something
    }
    if root.Val < target {
        BST(root.Right, target)
    }
    if root.Val > target {
        BST(root.Left, target)
    }
}

var BST = function(root, target) {
    if (root.val === target) {
        // found the target, do something
    }
    if (root.val < target) { 
        BST(root.right, target);
    }
    if (root.val > target) {
        BST(root.left, target);
    }
};

The framework of this code is quite similar to that of binary tree traversal, except it utilizes the characteristic of BST where the left node is smaller and the right node is larger. Next, let's see how the basic operations of this BST structure are implemented.

1. Validating the Legitimacy of a BST

LeetCode Problem 98 "Validate Binary Search Tree" requires you to determine if the given BST is valid:

98. Validate Binary Search Tree | LeetCode |

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

Note, there is a pitfall here. According to the characteristic of BST where the left node is smaller and the right node is larger, to determine if a node is a valid BST node, wouldn't it just compare itself with its left and right children? It seems like you should write the code like this:

boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    // the left side of the root should be smaller
    if (root.left != null && root.left.val >= root.val)
        return false;
    // the right side of the root should be larger
    if (root.right != null && root.right.val <= root.val)
        return false;

    return isValidBST(root.left)
        && isValidBST(root.right);
}

bool isValidBST(TreeNode* root) {
    if (root == nullptr) return true;
    // the left side of root should be smaller
    if (root->left != nullptr && root->left->val >= root->val)
        return false;
    // the right side of root should be bigger
    if (root->right != nullptr && root->right->val <= root->val)
        return false;

    return isValidBST(root->left)
        && isValidBST(root->right);
}

def isValidBST(root: TreeNode) -> bool:
    if root is None:
        return True
    # the left of root should be smaller
    if root.left is not None and root.left.val >= root.val:
        return False
    # the right of root should be larger
    if root.right is not None and root.right.val <= root.val:
        return False

    return isValidBST(root.left) and isValidBST(root.right)

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    // the left side of root should be smaller
    if root.Left != nil && root.Left.Val >= root.Val {
        return false
    }
    // the right side of root should be larger
    if root.Right != nil && root.Right.Val <= root.Val {
        return false
    }

    return isValidBST(root.Left)
        && isValidBST(root.Right)
}

var isValidBST = function(root) {
    if (root === null) return true;
    // the left side of the root should be smaller
    if (root.left !== null && root.left.val >= root.val)
        return false;
    // the right side of the root should be larger
    if (root.right !== null && root.right.val <= root.val)
        return false;

    return isValidBST(root.left)
        && isValidBST(root.right);
}

However, there is an error in this algorithm. In a Binary Search Tree (BST), each node should be smaller than all the nodes in its right subtree. The following binary tree is clearly not a BST because there is a node 6 in the right subtree of node 10, yet our algorithm incorrectly identifies it as a valid BST:

The error arises because, for each node root, the code only checks whether its left and right child nodes adhere to the rule of left being smaller than right. However, according to the definition of a BST, the entire left subtree of root must be smaller than root.val, and the entire right subtree must be larger than root.val.

The issue is that for a given node root, it can only directly manage its immediate left and right child nodes. How can we enforce root's constraints on its left and right subtrees? Please see the correct code below:

class Solution {
    public boolean isValidBST(TreeNode root) {
        return _isValidBST(root, null, null);
    }

    // Definition: This function returns whether all nodes in the
    // subtree rooted at 'root' satisfy max.val > root.val >
    public boolean _isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        // base case
        if (root == null) return true;
        // If root.val does not satisfy the max and min constraints, it is not a valid BST
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;
        // According to the definition, the maximum value for the left
        // subtree is root.val, and the minimum value for the right subtree
        return _isValidBST(root.left, min, root) 
            && _isValidBST(root.right, root, max);
    }
}

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return _isValidBST(root, nullptr, nullptr);
    }

    // Definition: This function returns whether all nodes in the
    // subtree rooted at root satisfy max->val > root->val >
    bool _isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
        // base case
        if (root == nullptr) return true;
        // If root->val does not satisfy the constraints of max and min, it is not a valid BST
        if (min != nullptr && root->val <= min->val) return false;
        if (max != nullptr && root->val >= max->val) return false;
        // According to the definition, the maximum value of the left
        // subtree is root->val and the minimum value of the right subtree
        return _isValidBST(root->left, min, root) 
            && _isValidBST(root->right, root, max);
    }
};

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self._isValidBST(root, None, None)

    # Definition: This function returns whether all nodes in the
    # subtree rooted at `root` satisfy max.val > root.val >
    def _isValidBST(self, root: TreeNode, min: TreeNode, max: TreeNode) -> bool:
        # base case
        if root is None:
            return True
        # If root.val does not comply with the constraints of max and min, it is not a valid BST
        if min is not None and root.val <= min.val:
            return False
        if max is not None and root.val >= max.val:
            return False
        # According to the definition, the maximum value of the left
        # subtree is root.val, and the minimum value of the right subtree
        return self._isValidBST(root.left, min, root) and self._isValidBST(root.right, root, max)

func isValidBST(root *TreeNode) bool {
    return _isValidBST(root, nil, nil)
}

// Definition: This function returns whether all nodes of the
// subtree rooted at root satisfy max.Val > root.Val > min.Val
func _isValidBST(root *TreeNode, min, max *TreeNode) bool {
    // base case
    if root == nil {
        return true
    }
    // If root.Val does not meet the constraints of max and min, it is not a valid BST
    if min != nil && root.Val <= min.Val {
        return false
    }
    if max != nil && root.Val >= max.Val {
        return false
    }
    // By definition, limit the maximum value of the left subtree to
    // root.Val and the minimum value of the right subtree to
    return _isValidBST(root.Left, min, root) && _isValidBST(root.Right, root, max)
}

var isValidBST = function(root) {
    return _isValidBST(root, null, null);
};

// Definition: This function returns whether all nodes in the
// subtree rooted at 'root' satisfy max.val > root.val > min.val
var _isValidBST = function(root, min, max) {
    // base case
    if (root === null) return true;
    // If root.val does not meet the constraints of max and min, it is not a valid BST
    if (min !== null && root.val <= min.val) return false;
    if (max !== null && root.val >= max.val) return false;
    // According to the definition, the maximum value of the left subtree
    // is root.val, and the minimum value of the right subtree is root.val
    return _isValidBST(root.left, min, root) 
        && _isValidBST(root.right, root, max);
};

By using helper functions and expanding the function parameter list to carry extra information, we can pass constraints to all nodes of the subtree. This is a small technique in binary tree algorithms.

Searching for Elements in a BST

LeetCode Problem 700 "Search in a Binary Search Tree" requires you to search for a node with the value target in a BST. The function signature is as follows:

TreeNode searchBST(TreeNode root, int target);

TreeNode* searchBST(TreeNode* root, int target);

def searchBST(root: TreeNode, target: int) -> TreeNode:

func searchBST(root *TreeNode, target int) *TreeNode {
    // Implementation goes here
}

var searchBST = function(root, target) {}

If you are searching in a regular binary tree, you can write the code like this:

TreeNode searchBST(TreeNode root, int target) {
    if (root == null) return null;
    if (root.val == target) return root;
    // if the current node is not found, recursively search the left and right subtrees
    TreeNode left = searchBST(root.left, target);
    TreeNode right = searchBST(root.right, target);

    return left != null ? left : right;
}

TreeNode* searchBST(TreeNode* root, int target) {
    if (root == nullptr) return nullptr;
    if (root->val == target) return root;
    // if the current node is not found, recursively search the left and right subtrees
    TreeNode* left = searchBST(root->left, target);
    TreeNode* right = searchBST(root->right, target);
    return left != nullptr ? left : right;
}

def searchBST(root, target):
    if not root:
        return None
    if root.val == target:
        return root
    # if the current node is not found, recursively search the left and right subtrees
    left = searchBST(root.left, target)
    right = searchBST(root.right, target)

    return left if left else right

func searchBST(root *TreeNode, target int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.val == target {
        return root
    }
    // recursively search left and right subtrees
    left := searchBST(root.left, target)
    right := searchBST(root.right, target)
    // if the target node is found in the left subtree,
    // return the left subtree; otherwise, return the right
    if left != nil {
        return left
    }
    return right
}

var searchBST = function(root, target) {
    if (root == null) return null;
    if (root.val == target) return root;
    // if the current node is not found, recursively search the left and right subtrees
    let left = searchBST(root.left, target);
    let right = searchBST(root.right, target);

    return left != null ? left : right;
};

Writing it this way is completely correct, but this code essentially exhausts all nodes and is suitable for all binary trees. So how can we make full use of the special properties of a BST and take advantage of the "left smaller, right larger" characteristic?

It's simple. In fact, you don't need to search both sides recursively. Similar to the binary search concept, you can eliminate one side based on the comparison between target and root.val. Let's slightly modify the above approach:

TreeNode searchBST(TreeNode root, int target) {
    if (root == null) {
        return null;
    }
    // search in the left subtree
    if (root.val > target) {
        return searchBST(root.left, target);
    }
    // search in the right subtree
    if (root.val < target) {
        return searchBST(root.right, target);
    }
    // the current node is the target value
    return root;
}

TreeNode* searchBST(TreeNode* root, int target) {
    if (root == nullptr) {
        return nullptr;
    }
    // search in the left subtree
    if (root->val > target) {
        return searchBST(root->left, target);
    }
    // search in the right subtree
    if (root->val < target) {
        return searchBST(root->right, target);
    }
    // the current node is the target value
    return root;
}

def searchBST(root: TreeNode, target: int) -> TreeNode:
    # if the binary tree is empty, return directly
    if not root:
        return None
    # search in the left subtree
    if root.val > target:
        return searchBST(root.left, target)
    # search in the right subtree
    if root.val < target:
        return searchBST(root.right, target)
    # the current node is the target value
    return root

func searchBST(root *TreeNode, target int) *TreeNode {
    // if the root node is nil, return nil
    if root == nil {
        return nil
    }
    // search in the left subtree
    if root.val > target {
        return searchBST(root.left, target)
    }
    // search in the right subtree
    if root.val < target {
        return searchBST(root.right, target)
    }
    // the current node is the target value
    return root
}

var searchBST = function(root,target) {
    if (root === null) {
        return null;
    }
    // search in the left subtree
    if (root.val > target) {
        return searchBST(root.left, target);
    }
    // search in the right subtree
    if (root.val < target) {
        return searchBST(root.right, target);
    }
    // target value equals the current node, return directly
    return root;
}

Inserting a Number into a BST

Operations on data structures involve traversal and access. Traversal is "finding" and access is "modifying". For this specific problem, inserting a number means first finding the insertion position and then performing the insertion operation.

Since BSTs typically do not have duplicate values, we generally do not insert existing values into a BST. The following code assumes that no duplicate values will be inserted into the BST.

In the previous problem, we summarized the traversal framework for BSTs, which is the "finding" part. We can directly use this framework and add the "modifying" operation.

Once modification is involved, it becomes similar to constructing a binary tree. The function should return a TreeNode type and should handle the return values of the recursive calls.

LeetCode problem 701 "Insert into a Binary Search Tree" is exactly this problem:

701. Insert into a Binary Search Tree | LeetCode |

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

• The number of nodes in the tree will be in the range [0, 104].
• -108 <= Node.val <= 108
• All the values Node.val are unique.
• -108 <= val <= 108
• It's guaranteed that val does not exist in the original BST.

Let's look at the solution code directly. You can understand it better with the help of comments and the visualization panel:

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            // find an empty spot to insert the new node
            return new TreeNode(val);
        }

        // go to the right subtree to find the insertion spot
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        // go to the left subtree to find the insertion spot
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        // return root, the upper level recursion will receive this as the child node
        return root;
    }
}

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {
            // find the empty position to insert the new node
            return new TreeNode(val);
        }

        // look for the insertion position in the right subtree
        if (root->val < val) {
            root->right = insertIntoBST(root->right, val);
        }
        // look for the insertion position in the left subtree
        if (root->val > val) {
            root->left = insertIntoBST(root->left, val);
        }
        // return root, the upper recursion will take the return value as a child node
        return root;
    }
};

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            # find an empty spot to insert the new node
            return TreeNode(val)
        # go to the right subtree to find the insertion position
        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)
        # go to the left subtree to find the insertion position
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        # return root, the upper level of
        # recursion will receive the return value
        return root

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        // find the empty position to insert the new node
        return &TreeNode{Val: val}
    }
    // find the position to insert in the right subtree
    if root.Val < val {
        root.Right = insertIntoBST(root.Right, val)
    }
    // find the position to insert in the left subtree
    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val)
    }
    // return root, the upper recursion will receive the return value as a child node
    return root
}

var insertIntoBST = function(root, val) {
    if (root === null) {
        // find the empty spot to insert the new node
        return new TreeNode(val);
    }
    // find the insertion spot in the right subtree
    if (root.val < val) {
        root.right = insertIntoBST(root.right, val);
    }
    // find the insertion spot in the left subtree
    if (root.val > val) {
        root.left = insertIntoBST(root.left, val);
    }
    // return root, the upper recursion will receive the return value as a child node
    return root;
}

3. Deleting a Node in a BST

LeetCode Problem 450 "Delete Node in a BST" requires you to delete a node with a value of key in a Binary Search Tree (BST):

450. Delete Node in a BST | LeetCode |

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.

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, 104].
• -105 <= Node.val <= 105
• Each node has a unique value.
• root is a valid binary search tree.
• -105 <= key <= 105

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

This problem is a bit more complex. Similar to the insert operation, you first "find" and then "modify." Let's outline the framework first:

TreeNode deleteNode(TreeNode root, int key) {
    if (root.val == key) {
        // found it, proceed to delete
    } else if (root.val > key) {
        // go to the left subtree
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        // go to the right subtree
        root.right = deleteNode(root.right, key);
    }
    return root;
}

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root->val == key) {
        // found it, proceed to delete
    } else if (root->val > key) {
        // go to the left subtree
        root->left = deleteNode(root->left, key);
    } else if (root->val < key) {
        // go to the right subtree
        root->right = deleteNode(root->right, key);
    }
    return root;
}

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    if root.val == key:
        # Found it, proceed with deletion
    elif root.val > key:
        # Search in the left subtree
        root.left = deleteNode(root.left, key)
    elif root.val < key:
        # Search in the right subtree
        root.right = deleteNode(root.right, key)
    return root

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root.Val == key {
        // found it, proceed to delete
    } else if root.Val > key {
        // look in the left subtree
        root.Left = deleteNode(root.Left, key)
    } else if root.Val < key {
        // look in the right subtree
        root.Right = deleteNode(root.Right, key)
    }
    return root
}

var deleteNode = function(root, key) {
    if (root.val === key) {
        // Found it, proceed with deletion
    } else if (root.val > key) {
        // Go to the left subtree to search
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        // Go to the right subtree to search
        root.right = deleteNode(root.right, key);
    }
    return root;
}

Once the target node is found, say node A, the challenge is how to remove this node without disrupting the properties of the BST (Binary Search Tree). There are three scenarios, explained with diagrams.

Scenario 1: A is a leaf node with both child nodes being null. In this case, it can be removed directly.

if (root.left == null && root.right == null)
    return null;

Case 2: If A has only one non-empty child node, then it should let this child take its place.

// After excluding case 1
if (root.left == null) return root.right;
if (root.right == null) return root.left;

Case 3: A has two child nodes. This is tricky. To maintain the properties of the BST, A must be replaced by either the largest node in its left subtree or the smallest node in its right subtree. We will explain using the second approach.

if (root.left != null && root.right != null) {
    // find the minimum node in the right subtree
    TreeNode minNode = getMin(root.right);
    // replace root with minNode
    root.val = minNode.val;
    // then delete the minNode
    root.right = deleteNode(root.right, minNode.val);
}

After analyzing the three cases, fill in the framework and simplify the code:

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            // these two if statements correctly handle cases 1 and 2
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            // handle case 3
            // get the smallest node in the right subtree
            TreeNode minNode = getMin(root.right);
            // delete the smallest node in the right subtree
            root.right = deleteNode(root.right, minNode.val);
            // replace the root node with the smallest node in the right subtree
            minNode.left = root.left;
            minNode.right = root.right;
            root = minNode;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    TreeNode getMin(TreeNode node) {
        // the leftmost node in a BST is the smallest
        while (node.left != null) node = node.left;
        return node;
    }
}

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return nullptr;
        if (root->val == key) {
            // these two if statements correctly handle cases 1 and 2
            if (root->left == nullptr) return root->right;
            if (root->right == nullptr) return root->left;
            // handle case 3
            // get the smallest node in the right subtree
            TreeNode* minNode = getMin(root->right);
            // delete the smallest node in the right subtree
            root->right = deleteNode(root->right, minNode->val);
            // replace the root node with the smallest node in the right subtree
            minNode->left = root->left;
            minNode->right = root->right;
            root = minNode;
        } else if (root->val > key) {
            root->left = deleteNode(root->left, key);
        } else if (root->val < key) {
            root->right = deleteNode(root->right, key);
        }
        return root;
    }

    TreeNode* getMin(TreeNode* node) {
        // in a BST, the leftmost node is the smallest
        while (node->left != nullptr) node = node->left;
        return node;
    }
};

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if root == None:
            return None
        if root.val == key:
            # These two if statements correctly handle cases 1 and 2
            if root.left == None:
                return root.right
            if root.right == None:
                return root.left
            # handle case 3
            # get the smallest node in the right subtree
            minNode = self.getMin(root.right)
            # delete the smallest node in the right subtree
            root.right = self.deleteNode(root.right, minNode.val)
            # replace the root node with the smallest node in the right subtree
            minNode.left = root.left
            minNode.right = root.right
            root = minNode
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root

    def getMin(self, node: TreeNode) -> TreeNode:
        # The leftmost node in a BST is the smallest
        while node.left != None:
            node = node.left
        return node

// delete a node in a binary search tree
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == key {
        // these two if statements correctly handle cases 1 and 2
        if root.Left == nil {
            return root.Right
        }
        if root.Right == nil {
            return root.Left
        }
        // handle case 3
        // get the smallest node in the right subtree
        minNode := getMin(root.Right)
        // delete the smallest node in the right subtree
        root.Right = deleteNode(root.Right, minNode.Val)
        // replace the root node with the smallest node in the right subtree
        minNode.Left = root.Left
        minNode.Right = root.Right
        root = minNode
    } else if root.Val > key {
        root.Left = deleteNode(root.Left, key)
    } else if root.Val < key {
        root.Right = deleteNode(root.Right, key)
    }
    return root
}

// get the smallest node in the binary search tree
func getMin(node *TreeNode) *TreeNode {
    // the leftmost node in a BST is the smallest
    for node.Left != nil {
        node = node.Left
    }
    return node
}

var deleteNode = function(root, key) {
    if (root == null) return null;
    if (root.val == key) {
        // These two if-statements handle cases 1 and 2 correctly
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // handle case 3
        // get the smallest node in the right subtree
        let minNode = getMin(root.right);
        // delete the smallest node in the right subtree
        root.right = deleteNode(root.right, minNode.val);
        // replace the root node with the smallest node in the right subtree
        minNode.left = root.left;
        minNode.right = root.right;
        root = minNode;
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

// get the smallest node in the BST.
var getMin = function(node) {
    // the leftmost node in the BST is the smallest
    while (node.left != null) node = node.left;
    return node;
}

With this, the deletion operation is complete. Note that in the above code, situation 3 is handled by a series of slightly complex linked list operations that swap the root and minNode nodes:

// handle case 3
// get the minimum node of the right subtree
TreeNode minNode = getMin(root.right);
// delete the minimum node of the right subtree
root.right = deleteNode(root.right, minNode.val);
// replace the root node with the minimum node of the right subtree
minNode.left = root.left;
minNode.right = root.right;
root = minNode;

Some readers might wonder why replacing the root node is so troublesome. Wouldn't it be simpler to just change the val field? It seems more straightforward and easier to understand:

// handle case 3
// get the minimum node of the right subtree
TreeNode minNode = getMin(root.right);
// delete the minimum node of the right subtree
root.right = deleteNode(root.right, minNode.val);
// replace the root node with the minimum node of the right subtree
root.val = minNode.val;

For this specific algorithm problem, it is possible, but this operation is not perfect. We generally do not swap nodes by modifying the values inside the nodes. In practical applications, the data field inside a BST node is user-defined and can be very complex. As a data structure (a utility), the BST's operations should be decoupled from the data stored inside. Therefore, we prefer using pointer operations to swap nodes without concerning ourselves with the internal data.

To summarize briefly, through this article, we have outlined the following tips:

1. If the current node has an overall impact on the child nodes below, you can use auxiliary functions to extend the parameter list and pass information through parameters.

2. Master the methods for adding, deleting, searching, and updating in a BST.

3. When recursively modifying a data structure, you need to receive the return value of the recursive call and return the modified node.

That's it for this article. For more classic binary tree exercises and training in recursive thinking, please refer to the Special Practice on Recursion in the binary tree section.