My remove function is not working properly. When I try to remove the root node it removes another. Please help! I've bolded the remove function. // remove the node with the given key public void remove(Node root, Key key) { Node parent = null; Node cur = root; while (cur != null) { if (cur.key == key) { if (cur.left == null && cur.right == null) { if (parent == null) { root = null; } else if (parent.left == cur) { parent.left = null; } else { parent.right = null; } } else if (cur.right == null) { if (parent == null) { root = cur.left; } else if (parent.left == cur) { parent.left = cur.left; } else { parent.right = cur.left; } } else if (cur.left == null) { if (parent == null) { root = cur.right; } else if (parent.left == cur) { parent.left = cur.right; } else { parent.right = cur.right; } } else { Node suc = cur.right; while (suc.left != null) { suc = suc.left; } Node sucData = suc; cur = sucData; remove(root, suc.key); } return; } else if (cur.key.compareTo(key) < 0) { parent = cur; cur = cur.right; } else { parent = cur; cur = cur.left; } } return; } public static void main(String[] args) { Scanner input = new Scanner(System.in); BST bst = new BST(); System.out.println("Enter key value pairs for the BST (-1 to end):"); while(input.hasNext()) { int key = input.nextInt(); if(key == -1) break; String value = input.next(); bst.insert(key, value); } System.out.println(bst.root.key); System.out.println("The size of the BST is:" + bst.size()); System.out.println("The height of the tree is:" + bst.height(bst.root)); System.out.println("The node with the minimum key is:" + bst.getMin(bst.root)); System.out.println("The value stored at the minimum key is: " + bst.get(bst.getMin(bst.root))); System.out.println("The node with the maximum key is:" + bst.getMax(bst.root)); System.out.println("Removing the maximum key: "); bst.remove(bst.root, bst.getMax(bst.root)); System.out.println("This is the root: " + bst.root.key);// System.out.println("The height of the tree is:" + bst.height(bst.root)); System.out.println("Printing the tree nodes using inorder traversal"); bst.inorder(bst.root); System.out.println("The size of the BST after removal is:" + bst.size()); System.out.println("Removing the root node: "); System.out.println("This is the root: " + bst.root.key);// bst.remove(bst.root, bst.root.key); System.out.println("The size of the BST after removal is:" + bst.size()); System.out.println("The height of the tree after removing the root is:" + bst.height(bst.root)); bst.inorder(bst.root); System.out.println("Removing the right child of the root node: "); bst.remove(bst.root, bst.root.right.key); bst.inorder(bst.root); System.out.println("Size of the BST after removal is:" + bst.size()); System.out.println("This is the root: " + bst.root.key);// } }
My remove function is not working properly. When I try to remove the root node it removes another. Please help!
I've bolded the remove function.
// remove the node with the given key
public void remove(Node root, Key key)
{
Node parent = null;
Node cur = root;
while (cur != null)
{
if (cur.key == key)
{
if (cur.left == null && cur.right == null)
{
if (parent == null)
{
root = null;
}
else if (parent.left == cur)
{
parent.left = null;
}
else
{
parent.right = null;
}
}
else if (cur.right == null)
{
if (parent == null)
{
root = cur.left;
}
else if (parent.left == cur)
{
parent.left = cur.left;
}
else
{
parent.right = cur.left;
}
}
else if (cur.left == null)
{
if (parent == null)
{
root = cur.right;
}
else if (parent.left == cur)
{
parent.left = cur.right;
}
else
{
parent.right = cur.right;
}
}
else
{
Node suc = cur.right;
while (suc.left != null)
{
suc = suc.left;
}
Node sucData = suc;
cur = sucData;
remove(root, suc.key);
}
return;
}
else if (cur.key.compareTo(key) < 0)
{
parent = cur;
cur = cur.right;
}
else
{
parent = cur;
cur = cur.left;
}
}
return;
}
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
BST<Integer, String> bst = new BST<Integer, String>();
System.out.println("Enter key value pairs for the BST (-1 to end):");
while(input.hasNext())
{
int key = input.nextInt();
if(key == -1) break;
String value = input.next();
bst.insert(key, value);
}
System.out.println(bst.root.key);
System.out.println("The size of the BST is:" + bst.size());
System.out.println("The height of the tree is:" + bst.height(bst.root));
System.out.println("The node with the minimum key is:" + bst.getMin(bst.root));
System.out.println("The value stored at the minimum key is: " + bst.get(bst.getMin(bst.root)));
System.out.println("The node with the maximum key is:" + bst.getMax(bst.root));
System.out.println("Removing the maximum key: ");
bst.remove(bst.root, bst.getMax(bst.root));
System.out.println("This is the root: " + bst.root.key);//
System.out.println("The height of the tree is:" + bst.height(bst.root));
System.out.println("Printing the tree nodes using inorder traversal");
bst.inorder(bst.root);
System.out.println("The size of the BST after removal is:" + bst.size());
System.out.println("Removing the root node: ");
System.out.println("This is the root: " + bst.root.key);//
bst.remove(bst.root, bst.root.key);
System.out.println("The size of the BST after removal is:" + bst.size());
System.out.println("The height of the tree after removing the root is:" + bst.height(bst.root));
bst.inorder(bst.root);
System.out.println("Removing the right child of the root node: ");
bst.remove(bst.root, bst.root.right.key);
bst.inorder(bst.root);
System.out.println("Size of the BST after removal is:" + bst.size());
System.out.println("This is the root: " + bst.root.key);//
}
}
Step by step
Solved in 2 steps
