Delete Node from a BST

Given a root node reference of a BST and a key, delete the node with the given key from 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.

Note: Time complexity should be O(height of the tree).

Example:

 root = [5,3,6,2,4,null,7]
 key = 3
 
     5
    / \
   3   6
  / \   \
 2   4   7
 
 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 following BST.
 
     5
    / \
   4   6
  /     \
 2       7
 
 Another valid answer is [5,2,6,null,4,null,7].
 
     5
    / \
   2   6
    \   \
     4   7
  1. Recursively find the node that has to be deleted from the BST, while setting the left/right nodes equal to the returned subtree.
  2. Once the node is found, we have to handle the following cases:
    • Node doesn’t have left or right – return null.
    • The node only has the left subtree – return the left subtree.
    • The node only has the right subtree – return the right subtree.
    • The node has both left and right subtree – find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value from the right subtree.
 public TreeNode deleteNode(TreeNode root, int key) {
     if(root == null){
         return null;
     }
     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;
         }else if(root.right == null){
             return root.left;
         }    
         TreeNode minNode = findMin(root.right);
         root.val = minNode.val;
         root.right = deleteNode(root.right, root.val);
     }
     return root;
 }
 
 private TreeNode findMin(TreeNode node){
     while(node.left != null){
         node = node.left;
     }
     return node;
 }

Categories: Binary Tree

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s