Results 1 to 3 of 3
 11172012, 09:35 AM #1Member
 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); } }
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(); } }
Thanks for your help.
 11182012, 03:27 AM #2Member
 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; 11182012 at 04:53 AM.
 11202012, 12:43 AM #3Member
 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; }
Similar Threads

How to sample a node from a binary tree efficiently?
By malaguena in forum Advanced JavaReplies: 0Last Post: 03122011, 05:57 PM 
Binary search tree
By hansmoolman in forum New To JavaReplies: 2Last Post: 10282010, 01:59 PM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 07:40 AM 
Binary search tree search method
By chopo1980 in forum New To JavaReplies: 2Last Post: 12102009, 01:42 AM 
Binary Search Tree
By michael_mke in forum New To JavaReplies: 3Last Post: 12042008, 02:03 AM
Bookmarks