Authors:
Stuart Reges, Marty Stepp
Chapter:
Binary Trees
Exercise:
Exercises
Question:16 | ISBN:9780136091813 | Edition: 2
Question
Write a method called trim that accepts minimum and maximum integers as parameters and removes from the tree any elements that are not within that range inclusive. For this method you should assume that your tree is a binary search tree and that its elements are in valid binary search tree order. Your method should maintain the binary search tree ordering property of the tree. This property is important for solving this problem.
Add the above method to the IntTree class from this chapter. You may define additional private methods to implement your public method if necessary. Several problem descriptions refer to the following reference binary trees:
Answer
Implementation of trim method:
public void trim(int minimum, int maximum)
{
overallRoot = trim(overallRoot, minimum, maximum);
}
private IntTreeNode trim(IntTreeNode root,
int minimum, int maximum)
{
if(root == null)
{
return root;
}
if(root.data <= maximum && root.data >= minimum)
{
root.left = trim(root.left, minimum, maximum);
root.right = trim(root.right, minimum, maximum);
return root;
}
else if(root.data < minimum)
{
return trim(root.right, minimum, maximum);
}
else if(root.data > maximum)
{
return trim(root.left, minimum, maximum);
}
else
{
return root;
}
}