Vultr DocsLatest Content

Delete Node in a BST

Updated on 21 May, 2025
Delete Node in a BST header image

Problem Statement

The task is to modify a Binary Search Tree (BST) by deleting a specific node characterized by a given key. The function will be provided a reference to the root node of the BST and the target key to be deleted. Post-deletion, the function should return the root node reference of the potentially modified BST. The operation involves two primary steps: locating the node to be deleted based on the key and, if found, removing it efficiently while ensuring the BST properties are maintained.

Examples

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

Approach and Intuition

To approach the problem of deleting a node from a BST without compromising the tree's structural and ordering properties, an intuitive step-wise method can be adopted:

  1. Search for the Target Node:

    • Traverse the tree starting from the root. Compare the key with the current node's value.
    • If the key is less than the current node’s value, proceed to the left child.
    • If the key is greater, move to the right child.
    • If the key matches the current value, the target node is found.

  2. Delete the Node:

    • If the node to be deleted has no children, simply remove the node.
    • If the node has one child, remove the node and link its parent to its child.
    • If the node has two children, find the in-order successor of the node (smallest node in the right subtree), copy its value to the target node, then recursively delete the in-order successor. This maintains the BST properties.

The examples provided illustrate different scenarios:

  • Example 1: The node with the value 3 is found and successfully deleted. The BST adjusts by either promoting one of the child nodes or rearranging the nearby nodes to maintain order. Two variations are possible in the final structure, reflecting flexibility in handling two-child deletions.
  • Example 2: The given key 0 is not found in the tree, so the tree remains unchanged.
  • Example 3: An empty tree scenario, where no action is taken as there are no nodes to search or delete.

Considering the constraints, the solution is expected to handle cases varying from empty trees to trees with a large number of nodes, ensuring robust performance across different scenarios, accounting for the extremities based on the node value limits provided. This approach leverages the properties of BSTs, primarily the ordered nature, to efficiently locate and remove nodes, using recursive strategies for complex deletions involving two children.

Solutions

  • Java
  • Python
java 
class Solution {
  public int findSuccessor(TreeNode node) {
    node = node.right;
    while (node.left != null) node = node.left;
    return node.val;
  }

  public int findPredecessor(TreeNode node) {
    node = node.left;
    while (node.right != null) node = node.right;
    return node.val;
  }

  public TreeNode removeNode(TreeNode node, int key) {
    if (node == null) return null;

    if (key > node.val) node.right = removeNode(node.right, key);
    else if (key < node.val) node.left = removeNode(node.left, key);
    else {
      if (node.left == null && node.right == null) node = null;
      else if (node.right != null) {
        node.val = findSuccessor(node);
        node.right = removeNode(node.right, node.val);
      }
      else {
        node.val = findPredecessor(node);
        node.left = removeNode(node.left, node.val);
      }
    }
    return node;
  }
}

The provided Java code implements a solution for deleting a node from a Binary Search Tree (BST). Below is a breakdown of how the deletion process operates and utilizes helper methods to handle different scenarios within the tree structure:

  1. Helper Methods:

    • findSuccessor(TreeNode node): Finds the in-order successor of the given node, which is the smallest value in the right subtree. It continues moving left until it finds the leftmost node in the right subtree.
    • findPredecessor(TreeNode node): Identifies the in-order predecessor of the given node, which is the largest value in the left subtree. It continues to move to the rightmost node in the left subtree.

  2. Core Method – removeNode(TreeNode node, int key):

    • Checks if the current node is null, returning null, indicating the node with the key doesn't exist.
    • Determines if the node to be deleted is located in the left subtree, right subtree, or is the current node based on comparisons with key.
    • Handles three scenarios for node deletion:
      • Leaf Node: Directly sets the node to null when both left and right children are null.
      • One Child (right): Replaces the node's value with its successor's value and then recursively deletes the successor.
      • One Child (left): Replaces the node's value with its predecessor's value and then recursively deletes the predecessor.
    • Returns the potentially new subtree after the adjustments for the removal or linkage.

This implementation efficiently manages the different cases encountered when removing elements from a BST, preserving the properties of BST whereby for any node, all values in the left subtree are less, and all values in the right subtree are greater than the node's value. The recursive approach ensures that these properties hold true after any modification, such as deletion.

python 
class Solution:
    # Find next higher value node
    def findSuccessor(self, node: TreeNode) -> int:
        node = node.right
        while node.left:
            node = node.left
        return node.val

    # Find next lower value node
    def findPredecessor(self, node: TreeNode) -> int:
        node = node.left
        while node.right:
            node = node.right
        return node.val

    def removeNode(self, node: TreeNode, target: int) -> TreeNode:
        if not node:
            return None

        # If target is greater, go right
        if target > node.val:
            node.right = self.removeNode(node.right, target)
        # If target is smaller, go left
        elif target < node.val:
            node.left = self.removeNode(node.left, target)
        # Found the node to delete
        else:
            # Node has no children
            if not (node.left or node.right):
                node = None
            # Node has a right child
            elif node.right:
                node.val = self.findSuccessor(node)
                node.right = self.removeNode(node.right, node.val)
            # Node has no right child but has a left child
            else:
                node.val = self.findPredecessor(node)
                node.left = self.removeNode(node.left, node.val)
                        
        return node

This solution outlines an approach to remove a specific node from a Binary Search Tree (BST) using Python. The main function to focus on is removeNode, which facilitates the deletion process based on the value of the node you want to remove.

  • The removeNode function checks if the current node is None, returning None if it is, which handles the base case of the recursion when the node does not exist in the tree.

  • Depending on whether the target value is greater than or less than the current node's value, it recursively searches the right or left subtree, respectively.

  • If the node to be removed is found (i.e., target == node.val), there are three situations:

    • If the node is a leaf (no children), it is simply removed by assigning None.
    • If the node has a right child, the node's value is replaced with its in-order successor's value (the smallest value in the right subtree). This keeps the BST properties intact. Then, the successor node itself is removed by a recursive call.
    • If the node has no right child but has a left child, the process is similar but uses the in-order predecessor (the largest value in the left subtree).

  • Auxiliary helper functions findSuccessor and findPredecessor are used to find the next higher or lower value in the BST, which are crucial for maintaining the BST properties after a node deletion.

This implementation ensures that the structure and properties of the BST remain valid after the deletion of a node, handling different scenarios of node configurations (children presence) efficiently. The recursion assists in navigating through the tree and making the necessary adjustments post-deletion.

Comments

No comments yet.