Using recursion to to trim a binary tree based on a given min and max value
- by Justin
As the title says, I have to trim a binary tree based on a given min and max value. Each node stores a value, and a left/right node. I may define private helper methods to solve this problem, but otherwise I may not call any other methods of the class nor create any data structures such as arrays, lists, etc.
An example would look like this:
overallRoot
_____[50]____________________
/ \
__________[38] _______________[90]
/ \ /
_[14] [42] [54]_____
/ \ \
[8] [20] [72]
\ / \
[26] [61] [83]
trim(52, 65);
should return:
overallRoot
[54]
\
[61]
My attempted solution has three methods:
public void trim(int min, int max) {
rootFinder(overallRoot, min, max);
}
First recursive method finds the new root perfectly.
private void rootFinder(IntTreeNode node, int min, int max) {
if (node == null)
return;
if (overallRoot.data < min) {
node = overallRoot = node.right;
rootFinder(node, min, max);
}
else if (overallRoot.data > max) {
node = overallRoot = node.left;
rootFinder(node, min, max);
}
else
cutter(overallRoot, min, max);
}
This second method should eliminate any further nodes not within the min/max, but it doesn't work as I would hope.
private void cutter(IntTreeNode node, int min, int max) {
if (node == null)
return;
if (node.data <= min) {
node.left = null;
}
if (node.data >= max) {
node.right = null;
}
if (node.data < min) {
node = node.right;
}
if (node.data > max) {
node = node.left;
}
cutter(node.left, min, max);
cutter(node.right, min, max);
}
This returns:
overallRoot
[54]_____
\
[72]
/
[61]
Any help is appreciated. Feel free to ask for further explanation as needed.
