# Delete Node in a BST

• A straight forward solution for searching for the given key in a BST and deleting it.

``````TreeNode deleteNode(TreeNode root, int key){
//General sanity check and if you ever run into a null node, just turn back
if(root == null)
return root;

/*
* Check if the given key is lesser than the root's key, if yes, go down its left subtree
* else if the key is bigger than the root's key, then go down its right subtree
*/

if(key < root.val)
root.left = deleteNode(root.left, key);
else if(key > root.val)
root.right = deleteNode(root.right,key);
else{
//If you have reached the node that you're searching for, 2 conditions arise

//1. Suppose the node has 0 or 1 children
if(root.left ==null || root.right == null){
TreeNode temp = null;

//If there is not left subtree, assign the right subtree to the temp
if(root.left == null)
temp = root.right;
else
temp = root.left;

//Now rewrite the current node (which you wanted to delete) with its children
root = temp;
}else{
/*
* 2. Suppose the node has 2 children, then travel down its right subtree and
* get the next In-Order successor. Basically, get the smallest node
* in the current node's right subtree
*/
TreeNode next = getMin(root.right);

//Overwrite current node's key with the successor's key
root.val = next.val;

//Now delete the original successor from the right subtree
root.right = deleteNode(root.right, next.val);
}
}
return root;
}

/*
* Utility function to get the smallest node in a BST
*/
TreeNode getMin(TreeNode root){
if(root != null){
while(root.left != null)
root = root.left;
}
return root;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.