Question

do a code trace on how a key gets deleted

package interview;

import java.util.*;

public class binarySearchTree {

Node root;

void insert(int key) {

root = insertRec(root,key);

}

void delete(int key) {

root = deleteRec(root,key);

}

Node insertRec(Node root, int key) {

if(root == null) {

root = new Node(key);

return root;

}

if(key < root.key) {

root.leftChild = insertRec(root.leftChild,key);

}

else if(key > root.key){

root.rightChild = insertRec(root.rightChild,key);

}

return root;

}

Node deleteRec(Node root, int key) {

if(root == null) {

return root;

}

if(key < root.key) {

root.leftChild = deleteRec(root.leftChild,key);

}

else if(key > root.key) {

root.rightChild = deleteRec(root.rightChild,key);

}

else {

if(root.leftChild == null) {

return root.rightChild;

}

else if(root.rightChild == null) {

return root.leftChild;

}

root.key = minValue(root.rightChild);

root.rightChild = deleteRec(root.rightChild, root.key);

}

return root;

}

int minValue(Node root){

int minV = root.key;

while(root.leftChild != null) {

minV = root.leftChild.key;

root = root.leftChild;

}

return minV;

}

void inorder() {

inorderRec(root);

}

void inorderRec(Node root) {

if(root != null) {

inorderRec(root.leftChild);

System.out.println(root.key);

inorderRec(root.rightChild);

}

}

public static void main(String[] args) {

binarySearchTree tree1 = new binarySearchTree();

tree1.insert(43);

tree1.insert(22);

tree1.insert(39);

tree1.insert(17);

tree1.insert(10);

tree1.insert(28);

System.out.println("In order traversal of the binary search tree: ");

tree1.inorder();

System.out.println("\n");

System.out.println("Delete 39 from the tree!");

System.out.println("In order traversal after deletion of the tree: ");

tree1.delete(22);

tree1.inorder();

}

class Node{

int key;

Node rightChild;

Node leftChild;

Node(int key){

this.key = key;

rightChild = null;

leftChild = null;

}

}

}

Answer 1

Basically this a binary search tree. The function responsible for deletion are delete and deleteRec

///////////////////////////////////

void delete(int key) {

root = deleteRec(root,key);

}

The above first is just calling deleteRec with root and node value to delete

//////////////////////////////////////////////

Node deleteRec(Node root, int key) {

if(root == null) {

return root;

}

if(key < root.key) {

root.leftChild = deleteRec(root.leftChild,key);

}

else if(key > root.key) {

root.rightChild = deleteRec(root.rightChild,key);

}

else {

if(root.leftChild == null) {

return root.rightChild;

}

else if(root.rightChild == null) {

return root.leftChild;

}

root.key = minValue(root.rightChild);

root.rightChild = deleteRec(root.rightChild, root.key);

}

return root;

}

To delete 39 was just printed in the statement System.out.println("Delete 39 from the tree!");

but actually delete is called for 22

tree1.delete(22);

Here is how the deleteRec is taking steps to delete

BST after insertion:

43

22   

17 39

10    28

A empty box represents now children in that place

so delete(22) calls

deleteRec(43,22)

if(root == null) False

if(key < root.key) True

{

root.leftChild = deleteRec(root.leftChild,key);

}

so, deleteRec(22,22) will be called

if(root == null) False

if(key < root.key) False

else if(key > root.key) False

else { True

if(root.leftChild == null) False

else if(root.rightChild == null) False

root.key = minValue(root.rightChild);   

right child of 22 is 39

so minValue(39)

so minvalue returns 28

root.key = 28 //chaning the value of root from 22 to 28

root.rightChild = deleteRec(root.rightChild, root.key); ---------------------- point reference 1

}

Tree becomes

43

28   

17 39

10    28

so deleteRec(root.rightChild, root.key);

so deleteRec(28, 28);

if(root == null) False

if(key < root.key) False

else if(key > root.key) False

else {

if(root.leftChild == null) True {

return root.rightChild;

}

Null will be returned here to the call deleteRec(28, 28);

so,   point reference 1

root.rightChild = Null

So Tree becomes

43

28   

17 39

10    Null

// The new tree is

43

28   

17 39

10