13. How would you delete a node in a binary search tree?

Basic

13. How would you delete a node in a binary search tree?

Overview

Deleting a node from a binary search tree (BST) is a fundamental operation in data structures, crucial for maintaining the correct order and structure of the tree. This operation ensures that the tree remains a valid BST after the deletion, where every node follows the BST property: the left subtree has nodes with keys less than the node's key, and the right subtree has nodes with keys greater than the node's key.

Key Concepts

  1. BST Properties: Understanding how BST maintains its properties during insertion, search, and deletion operations.
  2. Node Deletion Cases: Handling different cases of node deletion - deleting a leaf node, a node with one child, and a node with two children.
  3. Tree Balancing: Considering how deletion might affect the balance of the tree and the potential need for re-balancing.

Common Interview Questions

Basic Level

  1. What are the steps to delete a node in a binary search tree?
  2. How do you delete a leaf node from a BST?

Intermediate Level

  1. How do you delete a node with one child in a BST?

Advanced Level

  1. How do you handle the deletion of a node with two children in a BST?

Detailed Answers

1. What are the steps to delete a node in a binary search tree?

Answer: Deleting a node in a BST involves several steps, depending on the node's position and children. The basic steps are:
1. Find the node to be deleted.
2. Determine the number of children of the node.
- No children (Leaf node): Simply remove the node from the tree.
- One child: Remove the node and replace it with its child.
- Two children: Find the in-order successor (smallest node in the right subtree) or the in-order predecessor (largest node in the left subtree), swap it with the node to be deleted, and then delete the node from its new position which now has at most one child.

Key Points:
- Deleting a leaf node is straightforward as it does not affect the structure of the rest of the tree.
- When deleting a node with one child, you directly connect the child with the node's parent.
- Dealing with a node with two children requires a careful approach to maintain the BST properties.

Example:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode DeleteNode(TreeNode root, int key) {
        if (root == null) return null;

        // Find the node to be deleted.
        if (key < root.val) {
            root.left = DeleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = DeleteNode(root.right, key);
        } else {
            // Node with only one child or no child
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;

            // Node with two children: Get the inorder successor
            root.val = MinValue(root.right);

            // Delete the inorder successor
            root.right = DeleteNode(root.right, root.val);
        }
        return root;
    }

    int MinValue(TreeNode node) {
        int minv = node.val;
        while (node.left != null) {
            minv = node.left.val;
            node = node.left;
        }
        return minv;
    }
}

2. How do you delete a leaf node from a BST?

Answer: Deleting a leaf node from a BST is the simplest deletion scenario. A leaf node has no children, so you can directly remove it without affecting the structure of the tree.

Key Points:
- Check if the node is a leaf node.
- If it is, you can safely remove it by setting its parent's corresponding child pointer to null.

Example:

public TreeNode DeleteLeafNode(TreeNode root, int key) {
    if (root == null) return null;

    if (key < root.val) root.left = DeleteLeafNode(root.left, key);
    else if (key > root.val) root.right = DeleteLeafNode(root.right, key);
    else {
        // If the node is a leaf
        if (root.left == null && root.right == null) root = null;
    }

    return root;
}

[Repeat structure for questions 3-4]

For the sake of brevity, detailed answers for questions 3 and 4 are not included here. However, the approach for deleting a node with one child involves replacing the node with its single child, while deleting a node with two children involves finding the in-order successor or predecessor, swapping values, and then performing the deletion where the node now has fewer children, as illustrated in the detailed answer to question 1.

logo