# Thread: Binary Search Tree - Delete Node Iteratively

1. Member
Join Date
Feb 2011
Posts
17
Rep Power
0

## Binary Search Tree - Delete Node Iteratively

My code works recursively for deletion:

Java Code:
```	public void delete(K key) throws KeyNotFoundException{
root = delete(root, key);
}

protected bstNode<K,V> delete(bstNode<K,V> T, K key){
if (T != null){
if (key.compareTo(T.key) < 0){
T.left = delete(T.left, key);
}else if (key.compareTo(T.key) > 0){
T.right = delete(T.right, key);
}else{
this.BSTSize--;
if (T.left == null && T.right == null){
T = null;
}else if (T.left == null){
T = T.right;
}else if (T.right == null){
T = T.left;
}else{
bstNode<K,V> minNode = getMin(T.right);
T.key = minNode.key;
T.value = minNode.value;
T.right = delete(T.right, T.key);
}
}
}else{
throw new KeyNotFoundException();
}
return T;
}

public bstNode<K,V> getMin() {
return getMin(root);
}

protected bstNode<K,V> getMin(bstNode<K,V> T) {
if (T == null) {
return null;
} else if (T.left == null) {
return T;
} else {
return getMin(T.left);
}
}```
Here is my attempt of doing it iteratively:

Java Code:
```public void delete(K key) throws KeyNotFoundException{
if (root != null){
bstNode<K,V> deleteNode = root;
while (deleteNode != null){
if (key.compareTo(deleteNode.key) < 0){
deleteNode = deleteNode.left;
return;
}else if (key.compareTo(deleteNode.key) > 0){
deleteNode = deleteNode.right;
return;
}else{
this.BSTSize--;
if (deleteNode.left == null && deleteNode.right == null){
deleteNode = null;
}else if (deleteNode.left == null){
deleteNode = deleteNode.right;
}else if (deleteNode.right == null){
deleteNode = deleteNode.left;
}else{
bstNode<K,V> minNode = getMin(deleteNode.right);
deleteNode.key = minNode.key;
deleteNode.value = minNode.value;
//*I don't know how to do it here with two children*
}
}
}
}else{
throw new KeyNotFoundException();
}
}```
I don't know how to work with a node if it has two children (iteratively). I think the other parts seem OK.

2. Member
Join Date
Feb 2011
Posts
17
Rep Power
0

## Re: Binary Search Tree - Delete Node Iteratively (RESOLVED)

*Code will be posted after the assignments due date*
Last edited by benn22; 11-18-2012 at 05:53 AM.

3. Member
Join Date
Feb 2011
Posts
17
Rep Power
0

## Re: Binary Search Tree - Delete Node Iteratively (RESOLVED)

As promised:
Java Code:
```	@Override
public void delete(K key) throws KeyNotFoundException{
bstNode<K,V> parent = null;
bstNode<K,V> child = root;
bstNode<K,V> node = root;
while (node != null && node.key != key){
parent = node;
if (key.compareTo(node.key) < 0)
node = node.left; //Scan left
else
node = node.right; //Scan right
}

if (node == null)
throw new KeyNotFoundException();

//key found, work with their children
if (node.left == null && node.right == null){
if (parent == null)
root = null;
else if (key.compareTo(parent.key) < 0)
parent.left = null;
else
parent.right = null;
}else if (node.left == null){ //If left child is null, get right child
child = node.right;
swapKeys(node, child);
swapValues(node, child);
node.left = child.left;
node.right = child.right;
}else if (node.right == null){ //If right child is null, get left child
child = node.left;
swapKeys(node, child);
swapValues(node, child);
node.left = child.left;
node.right = child.right;
}else{ //If two children
child = node.left;
parent = null;
while (child.right != null){
parent = child;
child = parent.right;
}
if (parent == null){
swapKeys(node, child);
swapValues(node, child);
node.left = child.left;
}else{
swapKeys(node, child);
swapValues(node, child);
parent.right = child.left;
}
}
}

private void swapKeys(bstNode<K,V> node, bstNode<K,V> child){
K temp = node.key;
node.key = child.key;
child.key = temp;
}

private void swapValues(bstNode<K,V> node, bstNode<K,V> child){
V temp = node.value;
node.value = child.value;
child.value = temp;
}```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•