Delete Node in a Binary Search Tree (BST) Editorial

Practice Problem Link: Delete Node in a Binary Search Tree (BST)

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given the root node of a binary search tree and a key, remove the key from the tree and return the root node.

Note: The tree contains only unique values. Do not assume that the key is present in the BST.

There can be multiple solutions. You can return the root node containing any of the solutions as long as the tree is a BST.

Approach

Find the given key in the BST recursively. If the key is present in the BST, then there will be two cases.

• Case 1: Node to be deleted has at max one child.

 In this case, simply replace the current node with the child node. If both the children are NULL then replace the current node with NULL.

• Case 2: Node to be deleted has two children

In this case, replace the current node with the right child. Now traverse to the leftmost leaf node of the right subtree of the current node and set the left pointer of that leaf node to the left child of the current node (Since all the values in the left subtree will be less than that of the right subtree).

Analysis

• Time Complexity: O(Height of BST)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

Node* removeFromBst(Node* root, int key) {
    if (root == NULL) {
		return NULL;
	}
	if (root->data > key) {
		root->left = removeFromBst(root->left, key);
		return root;
	} 
	if (root->data < key) {
		root->right = removeFromBst(root->right, key);
		return root;
	}
	if (root->left == NULL) {
		return root->right;
	} 
	if (root->right == NULL) {
		return root->left;
	}
	Node* currNode = root->right;
	while (currNode->left != NULL) {
		currNode = currNode->left;
	}
	currNode->left = root->left;
	return root->right;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/

	Node removeFromBst(Node root, int key) {
	    if (root == null) {
			return null;
		}
		if (root.data > key) {
			root.left = removeFromBst(root.left, key);
			return root;
		} 
		if (root.data < key) {
			root.right = removeFromBst(root.right, key);
			return root;
		}
		if (root.left == null) {
			return root.right;
		} 
		if (root.right == null) {
			return root.left;
		}
		Node currNode = root.right;
		while (currNode.left != null) {
			currNode = currNode.left;
		}
		currNode.left = root.left;
		return root.right;
	}
}