How to delete a node from a binary search tree

A binary search tree is a binary tree where the nodes are arranged such that the left sub-tree of a particular node will always contain nodes with values less than that node's value. Similarly, the right subtree of a particular node will always contain nodes with values greater than that node's value. These properties allow operations such as insertions, deletions, and searches to run in O(log(N))O(log(N)) time if the tree is balanced. However, if the tree is unbalanced, then these operations take O(N)O(N) time in the worst case.

Deletions

To delete a node with a value equal to val_to_delete , we first need to search for it. We compare val_to_delete with the value of each node as we proceed down the tree in search of our node to delete.

The example below illustrates how the node with a value equal to val_to_delete is found:

1 of 10

Once this node is found, we can proceed to delete it. There can be three possible scenarios when deleting a node from a binary search tree.

Scenario 1: Delete a leaf node

Deleting a leaf node is the simplest of scenarios. We don't need to account for any child nodes/subtrees. We can simply set the pointer to that node as NULL and delete the node. This is shown below:

1 of 5

Scenario 2: Delete a node with just one child

To delete a node xx with just one child yy, we need to make yy a child of x′sx's parent zz. Next, we can simply delete the pointer to node xx. This is illustrated below:

1 of 6

Scenario 3: Delete a node with two children

To delete a node xx with 2 children nodes, we need to find the node with the minimum value in x′sx's right subtree. Once this node min_right_subtree is found, we switch the values of min_right_subtree and xx(val_to_delete). Now, the node with value val_to_delete is the leaf node in x′sx's right subtree. This leaf node can simply be deleted as described above in scenario 1. This process is depicted below:

1 of 10

Example

The lines highlighted in the code below implement a function deleteNode() to delete a node with a particular value from a binary search tree:

  Node * deleteNode(Node * root, int val_to_delete) 
  {
    if (root == NULL) 
    {
      return NULL;
    }
    
    else
    {
      // node is found and needs to be deleted 
      if(val_to_delete == root->value) 
      {
        // scenario 1 
        if (root->left_child == NULL && root->right_child == NULL) 
        {
          delete root;
          return NULL;
        } 
        // scenario 2
        else if(root->left_child == NULL)
        {
          Node * temp = root->right_child;
          delete root;
          return temp;
        }
        // scenario 3
        else if (root->right_child == NULL) 
        {
          Node * temp = root->left_child;
          delete root;
          return temp;
        } 
        // scenario 4
        else 
        {
          // finding the minimum value in the right subtree
          Node * min_right_subtree ; 
          Node * current = root->right_child;
          while (current->left_child != NULL) 
          {
            current = current->left_child;
          }
          min_right_subtree = current;
        
          // switching the values 
          root->value = min_right_subtree->value;
          // Deleting the node with val_to_delete now as a leaf node
          root->right_child = deleteNode(root->right_child, min_right_subtree->value);
        }
      }
    
      // keep searching for node
      else
      {
        if (val_to_delete < root->value) 
        {
          root->left_child = deleteNode(root->left_child, val_to_delete);
        }
        
        else if (val_to_delete > root->value) 
        {
          root->right_child = deleteNode(root->right_child, val_to_delete);
        }
      }
      
      return root ;
    }
  }
};

Note: In the output of the code above, the nodes of the tree have been printed in a 2-D manner to help with visualization. To keep the implementation of the prettyPrintTree() function straightforward, the tree is rotated 90o to the left in the output.

Explanation

We have a function named deleteNode that takes two arguments, root of the tree and the val_to_delete, value to be delete. Let's see the code.

  • Lines 3-5: If the value of the root is NULL or the tree have no value, then the function will return NULL .

  • Lines 8-71: If the root has values, then keep searching and if the node with same value is found, delete the node and adjust the tree accordingly.

    • Lines 11-54: If the value of the node is found, then we have 4 scenarios.

      • Line 14-18: If the left and right child of the node are NULL, then we can simply delete the node and return NULL.

      • Line 21-26: If the value of the left child is NULL, then we can make a temporary node temp , assign the value of the right child, delete the current node and return the temp variable.

      • Line 29-34: If the value of the right child is NULL, then we can make a temporary node temp , assign the value of the left child, delete the current node and return the temp variable.

      • Line 37-54: If the node have both left and right child elements. We find the smallest value from the right subtree and replace the node with it.

        • Line 40: Declaring a variable min_right_subtree, to save the node with minimum value.

        • Line 41: Save the right subtree in a variable current, to iterate the tree for a minimum value node.

        • Line 42-45: Iterate the current to the left to reach the left-most leaf that holds the minimum value.

        • Line 46-49: Save the node to the min_right_subtree and its value to the root.

        • Line 52: We have replaced the value of the node with the minimum value from the right subtree. Now, we need to delete the node that holds the minimum value. We are calling the deleteNode function and passing the minimum value.

    • Lines 57-68: Search the node with the same value. If the value is less than the root value, then pass the left child of the root and call the deleteNode and vice versa.

    • Line 70: If the node is not found, then return the root.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved