How to write a method for deleting a node in a binary search tree? (Java) Hello,
ID: 3755724 • Letter: H
Question
How to write a method for deleting a node in a binary search tree? (Java)
Hello, I am dealing with a problem where I have to write binary search tree methods in the Java programming language. I have written insertInTree and removeSmallestNode methods, however I'm having difficulty with a remove node method with two children. Of course, I want only this node to be removed and the remaining nodes such as the children of this node to remain in the tree.
The instructions for trying to help figure it out are:
"
Since you can efficiently write removeMinimal() by simply transferring a subtree up one level, you can use that method to help you implement a general remove() method for a binary search tree.
Remember, you'll need to use the ordering property to know which side to recurse down, and after recursing you'll need to reassemble the tree.
But in the base case, the way to fix the tree will be different in the one (or no) child cases (by transferring) and the two child case (by reassembling the tree with a patch). Be careful not to destroy the tree after you've fixed it!
This is a hard method to write."
Any help would be appreciated!
Explanation / Answer
// Java code to remove a node from BinarySearchTree
public class BinarySearchTree {
// BTNode is the class that represent the node of the BinarySearchTree (consisting of data and pointers to left and right subtrees)
private BTNode root; // root of the tree
/* the remaining codes */
// method to delete a node with data
public void delete(int data)
{
// if tree is empty
if(isEmpty())
{
System.out.println(" Tree Empty");
}else if(!search(data))
System.out.println(" Data not found in tree");
else {
root = delete(data,root); // update the root after deletion
System.out.println(data+" deleted from tree");
}
}
// helper method to delete the node
private BTNode delete(int data,BTNode node)
{
BTNode p,n;
// if data is found, then delete the node
if( data == node.getData())
{
// get the left and right subtree
BTNode lt,rt;
lt = node.getLeft();
rt = node.getRight();
// if no children
if(lt == null && rt == null)
return null;
// if no left subtree, return right subtree
else if(lt == null)
return rt;
// if no right subtree, return left subtree
else if(rt == null)
return lt;
// if 2 children, make the left subtree as child of right subtree and replace the node with the right subtree
else {
p = rt;
while(p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return rt;
}
}
// if data is less than node, then look in left subtree
else if(data < node.getData())
{
n = delete(data,node.getLeft());
node.setLeft(n);
}
// if data is greater than node, then look in right subtree
else
{
n = delete(data,node.getRight());
node.setRight(n);
}
return node;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.