Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

BST Delete

Easy

0/40

Average time to solve is 15m

Contributed by

10 upvotes

Asked in companies

Problem statement

You are given a binary search tree (BST) and a key value 'K'. You need to delete the node with value 'K'. It is guaranteed that a node has the value 'K'.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Note:

All the elements of the binary search tree are unique.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T', the number of test cases.

The first line of every test case contains elements in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place.

The second line of every test case contains a single integer 'K' denoting the value of the node to be deleted. It is guaranteed that this value exists in the Binary Tree.

For example, the input for the tree depicted in the below image would be :

20 10 35 5 15 30 42 -1 -1 -1 13 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 20

Level 2 :
Left child of 20 = 10
Right child of 20 = 35

Level 3 :
Left child of 10 = 5
Right child of 10 = 15
Left child of 35 = 30
Right child of 35 = 42

Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 15 = null (-1)
Right child of 15 = 13
Left child of 30 = null (-1)
Right child of 30 = null (-1)
Left child of 42 = null (-1)
Right child of 42 = null (-1)

Level 5 :
Left child of 13 = null (-1)
Right child of 13 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. 

The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
20 10 35 5 15 30 42 -1 -1 -1 13 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, you need to return the head of the BST after deletion.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 1000 
1 <= data <= 10^9 and data != -1
1 <= K<= 10^9 

Time limit: 1 second

Sample Input 1:

3
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
6
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
5
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
7

Sample Output 1:

8 5 10 2 7 -1 -1 -1 -1 -1 -1
8 6 10 2 7 -1 -1 -1 -1 -1 -1
8 5 10 2 6 -1 -1 -1 -1 -1 -1

Explanation to sample input 1:

The given BST is the same for both the test cases.

For the first test case, we need to delete the node with value 6. After deletion, the BST would look like:

For the second test case, we need to delete the node with value 5. After deletion, the BST would look like:

For the third test case, we need to delete the node with value 7. After deletion, the BST would look like:

Sample Input 2 :

2
20 16 -1 12 -1 8 -1 4 -1 -1 -1 
12
1 2 3 -1 -1 -1 -1
3

Sample Output 2:

20 16 -1 8 -1 4 -1 -1 -1
1 2 -1 -1 -1

Hint 1

Hint 2

Think of a recursive solution.

Approaches (2)

Approach 1

Approach 2

Recursive Solution - 1

There can be three cases when a node is to be deleted:
- The node has 0 children/ node is a leaf. In this case, simply remove the node from the tree.
- The node has 1 child. In this case, delete the node and copy the child to this node.
- The node has 2 children. In this case, delete the node and copy the inorder successor to this node. (You could have also used the inorder predecessor).
To find the inorder successor node, we take the leftmost node of the right child.
We do this every time we find the node has two children.
Finally delete the given node and return the head of the new Binary Tree.

Time Complexity

O(H), where ‘N’ is the number of nodes in the binary tree and ‘H’ is the height of the Binary Tree.

In the worst case, the height can be ‘H’ = ‘N’, for a Skewed Binary Tree.

Space Complexity

O(H), Stack space for recursive calls of ‘N’ nodes of the binary tree, where ‘N’ is the number of nodes in the binary tree and ‘H’ is the height of the Binary Tree.

In the worst case, the height can be ‘H’ = ‘N’, for a Skewed Binary Tree.

(100% EXP penalty)

BST Delete

Raj Ghosh

Interview problems

JAVA SOLUTION || BST Delete ||

import java.util.* ;

import java.io.*;

public class Solution {

public static BinaryTreeNode<Integer> bstDelete(BinaryTreeNode<Integer> root, int key) {

if (root == null)

return root;

if (key < root.data) {

root.left = bstDelete(root.left, key);

} else if (key > root.data) {

root.right = bstDelete(root.right, key);

} else {

if (root.left == null) {

return root.right;

} else if (root.right == null) {

return root.left;

}

root.data = minValue(root.right);

root.right = bstDelete(root.right, root.data);

}

return root;

}

public static int minValue(BinaryTreeNode<Integer> root) {

int minValue = root.data;

while (root.left != null) {

minValue = Math.min(minValue, root.left.data);

root = root.left;

}

return minValue;

}

7 views

0 replies

0 upvotes

Rajkishor Kumar

Interview problems

C++ Easy Solution

// finding mini value

BinaryTreeNode<int>* minVal(BinaryTreeNode<int>* root){

BinaryTreeNode<int>* temp=root;

while(temp->left !=NULL){

temp=temp->left;

}

return temp;

}

BinaryTreeNode<int>* bstDelete(BinaryTreeNode<int>* root, int key) {

if(root==NULL) return root;

if(root->data==key){

// 0 child

if(root->left==NULL && root->right==NULL){

delete root;

return NULL;

}

// 1 left chile

if(root->left!=NULL && root->right==NULL){

BinaryTreeNode<int>* temp = root->left;

delete root;

return temp;

}

// 1 right child

if(root->left==NULL && root->right!=NULL){

BinaryTreeNode<int>* temp = root->right;

delete root;

return temp;

}

// 2 child

if(root->left!=NULL && root->right!=NULL){

int mini=minVal(root->right)->data;

root->data=mini;

root->right=bstDelete(root->right, mini);

return root;

}

else if(root->data >key){

// left part me jawo

root->left=bstDelete(root->left, key);

return root;

}

else{

// right part me jawo

root->right=bstDelete(root->right, key);

return root;

}

69 views

0 replies

0 upvotes

Soumadip Patra

Interview problems

Python Code

from os import *
from sys import *
from collections import *
from math import *

'''
  ----Binary tree node class for reference-----
    class BinaryTreeNode:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None

'''

def minValueNode(node):
  curr = node
  while curr.left is not None:
    curr = curr.left
  return curr

def bstDelete(root, key):
  # Write your code here.
   # Base case: if the tree is empty, return None
    if root is None:
        return root

    # If the key is smaller than the root's key, it lies in the left subtree
    if key < root.data:
        root.left = bstDelete(root.left, key)

    # If the key is larger than the root's key, it lies in the right subtree
    elif key > root.data:
        root.right = bstDelete(root.right, key)

    # If the key is the same as the root's key, then this is the node to be deleted
    else:
        # Case 1: Node with only one child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # Case 2: Node with two children
        # Get the inorder successor (smallest in the right subtree)
        temp = minValueNode(root.right)
        # Copy the inorder successor's content to this node
        root.data = temp.data
        # Delete the inorder successor
        root.right = bstDelete(root.right, temp.data)

    # Return the root node after deletion
    return root

19 views

0 replies

0 upvotes

Abhinendra Pratap Singh

Interview problems

BST Delete Python Solution

def bstDelete(root, key):

class BinaryTreeNode:

def __init__(self, data):

self.data = data

self.left = None

self.right = None

def minValueNode(node):

# Function to find the node with the minimum value in a given subtree

current = node

while current.left is not None:

current = current.left

return current

def bstDelete(root, key):

# Function to delete a node with a given key from the BST rooted at root

# Base case: if the tree is empty, return None

if root is None:

return root

# If the key is smaller than the root's key, it lies in the left subtree

if key < root.data:

root.left = bstDelete(root.left, key)

# If the key is larger than the root's key, it lies in the right subtree

elif key > root.data:

root.right = bstDelete(root.right, key)

# If the key is the same as the root's key, then this is the node to be deleted

else:

# Case 1: Node with only one child or no child

if root.left is None:

temp = root.right

root = None

return temp

elif root.right is None:

temp = root.left

root = None

return temp

# Case 2: Node with two children

# Get the inorder successor (smallest in the right subtree)

temp = minValueNode(root.right)

# Copy the inorder successor's content to this node

root.data = temp.data

# Delete the inorder successor

root.right = bstDelete(root.right, temp.data)

# Return the root node after deletion

return root

31 views

0 replies

0 upvotes

Syed Yakoob Shiraz

Interview problems

C++ solution uses inorder successor replacement technique

BinaryTreeNode<int>* bstDelete(BinaryTreeNode<int>* root, int key) {

// Write your code here

if(!root){

return nullptr;

}

if(root->data>key){

root->left = bstDelete(root->left, key);

return root;

}else if(root->data<key){

root->right = bstDelete(root->right, key);

return root;

}

if(!root->left){

BinaryTreeNode<int> *tmp = root->right;

delete root;

return tmp;

}

else if(!root->right){

BinaryTreeNode<int> *tmp = root->left;

delete root;

return tmp;

}else{

BinaryTreeNode<int> *par=root, *succ=root->right;

while(succ->left){

par = succ;

succ = succ->left;

}

if(par!=root){

par->left = succ->right;

}else{

par->right = succ->right;

}

root->data = succ->data;

delete succ;

return root;

}

103 views

0 replies

1 upvote

Thanesh Gola

Interview problems

C++ Solution(Easy Code)

#include <bits/stdc++.h>

/**********************************************************

Following is the Binary Tree Node class structure

template <typename T>

class BinaryTreeNode {

public :

T data;

BinaryTreeNode<T> *left;

BinaryTreeNode<T> *right;

BinaryTreeNode(T data) {

this -> data = data;

left = NULL;

right = NULL;

}

};

***********************************************************/

BinaryTreeNode<int>* minValue(BinaryTreeNode<int>* root){

BinaryTreeNode<int>* temp = root;

while(temp->left != NULL){

temp = temp->left;

}

return temp;

}

BinaryTreeNode<int>* bstDelete(BinaryTreeNode<int>* root, int key) {

if(root == NULL){

return root;

}

if(root->data == key){

// 0 child

if(root->left==NULL && root->right==NULL){

delete root;

return NULL;

}

// 1 child

if(root->left==NULL && root->right !=NULL){

BinaryTreeNode<int>* temp = root->right;

delete root;

return temp;

}

if(root->left !=NULL && root->right==NULL){

BinaryTreeNode<int>* temp = root->left;

delete root;

return temp;

}

// 2 child

if(root->left!=NULL && root->right!=NULL){

int mini = minValue(root->right)->data;

root->data = mini;

root->right = bstDelete(root->right, mini);

return root;

}

else if(root->data > key){

root->left = bstDelete(root->left, key);

return root;

}

else {

root->right = bstDelete(root->right, key);

return root;

}

234 views

0 replies

2 upvotes

Sarthak Jain

Interview problems

Java Easy Approach Solution

public class Solution {

public static BinaryTreeNode<Integer> bstDelete(BinaryTreeNode<Integer> root, int key) {

if (root == null)

return root;

if (key < root.data) {

root.left = bstDelete(root.left, key);

} else if (key > root.data) {

root.right = bstDelete(root.right, key);

} else {

if (root.left == null) {

return root.right;

} else if (root.right == null) {

return root.left;

}

root.data = minValue(root.right);

root.right = bstDelete(root.right, root.data);

}

return root;

}

public static int minValue(BinaryTreeNode<Integer> root) {

int minValue = root.data;

while (root.left != null) {

minValue = Math.min(minValue, root.left.data);

root = root.left;

}

return minValue;

}

201 views

0 replies

0 upvotes

Abhishek Kantharia

Interview problems

BST Delete 100% Working Solution

#include <bits/stdc++.h> 
/**********************************************************
Following is the Binary Tree Node class structure

        template <typename T>
        class BinaryTreeNode {
            public :
            T data;
            BinaryTreeNode<T> *left;
            BinaryTreeNode<T> *right;

            BinaryTreeNode(T data) {
                this -> data = data;
                left = NULL;
                right = NULL;
            }
        };

***********************************************************/

BinaryTreeNode<int>* findMinimum(BinaryTreeNode<int>* root) {
 if (root == NULL) {
   return NULL;
 }
 while (root->left != NULL) {
   root = root->left;
 }                                      	 		     		      return root;
}

                                        BinaryTreeNode<int>* bstDelete(BinaryTreeNode<int>* root, int data) {
                                            if (root == NULL) {
                                                    return NULL;
                                                        }
                                                            
                                                                if (root->data == data) {
                                                                        if (root->left == NULL && root->right == NULL) {
                                                                                    delete root;
                                                                                                return NULL;
                                                                                                        }
                                                                                                                if (root->left != NULL && root->right == NULL) {
                                                                                                                            BinaryTreeNode<int>* temp = root->left;
                                                                                                                                        delete root;
                                                                                                                                                    return temp;
                                                                                                                                                            }
                                                                                                                                                                    if (root->left == NULL && root->right != NULL) {
                                                                                                                                                                                BinaryTreeNode<int>* temp = root->right;
                                                                                                                                                                                            delete root;
                                                                                                                                                                                                        return temp;
                                                                                                                                                                                                                }
                                                                                                                                                                                                                        if (root->left != NULL && root->right != NULL) {
                                                                                                                                                                                                                                    BinaryTreeNode<int>* minimum = findMinimum(root->right);
                                                                                                                                                                                                                                                root->data = minimum->data;
                                                                                                                                                                                                                                                            root->right = bstDelete(root->right, minimum->data);
                                                                                                                                                                                                                                                                        return root;
                                                                                                                                                                                                                                                                                }
                                                                                                                                                                                                                                                                                    } else if (root->data > data) {
                                                                                                                                                                                                                                                                                            root->left = bstDelete(root->left, data);
                                                                                                                                                                                                                                                                                                } else {
                                                                                                                                                                                                                                                                                                        root->right = bstDelete(root->right, data);
                                                                                                                                                                                                                                                                                                            		}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 return root;
}

programming

beginners

263 views

0 replies

2 upvotes

Laxman Suthar

Interview problems

solution

BinaryTreeNode<int>* temp=root; while(temp->left!=NULL){ temp=temp->left; } return temp->data; }

BinaryTreeNode<int>* bstDelete(BinaryTreeNode<int>* root, int data) { // Write your code here if(root==NULL){ return NULL; } if(root->data==data){ if(root->left==NULL && root->right==NULL){ delete root; return NULL; } if(root->left!=NULL && root->right==NULL){ BinaryTreeNode<int>* temp=root->left; delete root; return temp; } if(root->left==NULL && root->right!=NULL){ BinaryTreeNode<int>* temp=root->right; delete root; return temp; } if(root->left!=NULL && root->right!=NULL){ int mini=minimum(root->right); root->data=mini; root->right= bstDelete(root->right,mini); return root; } } else if(root->data > data){ root->left= bstDelete(root->left,data); } else{ root->right=bstDelete(root->right,data); } return root;

185 views

0 replies

0 upvotes

Console