In section, we didn't quite have enough time to go over the removeMatchingLeaves problem. If you haven't already, I would go visit that link and read through the spec to make sure you understand what that problem is asking you.
To summarize, this problem is asking us to add a method to an IntTree. This method must accept another tree as a parameter, and must modify the current tree by removing all "matching leaves".
Later in this post, I'll talk about how we would write our method if the spec instead asked us to return a new tree where all matching leaves are removed in the new tree
So, I think part of the challenge of this question is figuring out how exactly you would end up recursing over two trees.
We'll start with the method header:
public void removeMatchingLeaves(IntTree other) {
}Notice that the type of the parameter is an IntTree, NOT an IntTreeNode. The IntTreeNode class is an internal detail
of IntTrees, and so wouldn't be something the client can directly pass in, even if they wanted to.
However, within the method, we do want to access the root, which is an IntTreeNode:
public void removeMatchingLeaves(IntTree other) {
this.root = this.helper(this.root, other.root);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
}Now, what I'll do is start by thinking of our different base cases. The first kind of base case I can think of
is when either self or other is null. If either are null, we can't really continue recursing, after all.
The next base case is when self is a leaf node. If self is a leaf node, then we might need to do the
"remove matching node" code, so it's a case we need to keep in mind.
Another possible base case is if other is a leaf node. However, if we think about this carefully, we really
don't need to do anything special in that case, so we can omit that check.
Using this information, we know we might try structuring our code like so:
public void removeMatchingLeaves(IntTree other) {
this.root = this.helper(this.root, other.root);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self == null || other == null) {
// One of the branches is null; stop recursing
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
} else {
// continue recursing
}
return self;
}Let's try filling this out backwards.
First, how do we continue recursing? Well, we can do the x = change(x) pattern thing:
public void removeMatchingLeaves(IntTree other) {
this.root = this.helper(this.root, other.root);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self == null || other == null) {
// One of the branches is null; stop recursing
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
} else {
// continue recursing
self.left = this.helper(self.left, other.left);
self.right = this.helper(self.right, other.right);
}
return self;
}Next, we can do the "remove matching" check:
public void removeMatchingLeaves(IntTree other) {
this.root = this.helper(this.root, other.root);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self == null || other == null) {
// One of the branches is null; stop recursing
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
if (self.data == other.data) {
self = null;
}
} else {
// continue recursing
self.left = this.helper(self.left, other.left);
self.right = this.helper(self.right, other.right);
}
return self;
}And finally, we have to handle the "stop recursing" case.
One possible way we could do this is to try setting self to null, just like in the leaf case. However,
this wouldn't work -- if other is null and self isn't, we still want to keep whatever subtree self is
referring to.
Instead, ultimately what we want to do is to return self. This will end up doing the correct thing in all cases --
if self is null, we still return null, otherwise, we return that entire subtree.
However, as it turns out, our code is already doing this! We already return self, so we'd actually want to leave that branch empty.
This means that our final, working version of the code looks like this:
public void removeMatchingLeaves(IntTree other) {
this.root = this.helper(this.root, other.root);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self == null || other == null) {
// One of the branches is null; stop recursing
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
if (self.data == other.data) {
self = null;
}
} else {
// continue recursing
self.left = this.helper(self.left, other.left);
self.right = this.helper(self.right, other.right);
}
return self;
}That said, having an empty branch is pretty bad style. This won't matter for the final, since style doesn't matter there, but if you did feel like cleaning up the code, we would need to modify it to look like this:
public void removeMatchingLeaves(IntTree other) {
this.root = this.helper(this.root, other.root);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self != null && other != null) {
if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
if (self.data == other.data) {
self = null;
}
} else {
// continue recursing
self.left = this.helper(self.left, other.left);
self.right = this.helper(self.right, other.right);
}
}
return self;
}Or alternatively, we could do something like this:
public void removeMatchingLeaves(IntTree other) {
this.root = this.helper(this.root, other.root);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self == null || other == null) {
// One of the branches is null; stop recursing
return self;
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
if (self.data == other.data) {
self = null;
} else {
return self;
}
} else {
// continue recursing
self.left = this.helper(self.left, other.left);
self.right = this.helper(self.right, other.right);
return self;
}
}The problem as written asked us to modify the original tree. But what if instead, it asked us to return a new tree? What would the code look like then?
The first thing we would need to change is the public pair to look like this:
public IntTree removeMatchingLeaves(IntTree other) {
IntTreeNode newRoot = this.helper(this.root, other.root);
return new IntTree(newRoot);
}Notice that we're now have a return type of IntTree (NOT IntTreeNode!), and that we don't set this.root in any way.
Next, we need to make our private pair contantly create a new node, instead of modifying anything in the original tree.
Just like before, we'll start backwards and handle the recursive case. In that particular case, we want to create an entirely new node, using our helper method to find out what our new left and right branches should be.
public IntTree removeMatchingLeaves(IntTree other) {
IntTreeNode newRoot = this.helper(this.root, other.root);
return new IntTree(newRoot);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self == null || other == null) {
// One of the branches is null; stop recursing
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
} else {
// continue recursing
return new IntTreeNode(
self.data,
this.helper(self.left, other.left),
this.helper(self.right, other.right));
}
}Next, the leaf case. We can handle that in almost the same way:
public IntTree removeMatchingLeaves(IntTree other) {
IntTreeNode newRoot = this.helper(this.root, other.root);
return new IntTree(newRoot);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (self == null || other == null) {
// One of the branches is null; stop recursing
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
if (self.data == other.data) {
return null;
} else {
return new IntTreeNode(self.data);
}
} else {
// continue recursing
return new IntTreeNode(
self.data,
this.helper(self.left, other.left),
this.helper(self.right, other.right));
}
}And finally, the "what if either branch is null" check. This part is trickier because we can no longer simply return
self -- we want to create an entirely new tree without sharing any nodes. (If we did share nodes, that would mean that
modifying one tree later on would also modify the original, which seems like the sort of thing that would make the client
pretty unhappy).
So now, the new behavior we want is to continue recursing down self if we can, creating new nodes. Or to rephrase, if
other is null, we will always create a new node without doing any checks. That said, we will still eventually need to check
if self is null or not, since we don't want to continue recursing when self is null.
We can express all this by slightly tweaking our if statement condition and adding a new if/else, like so:
public IntTree removeMatchingLeaves(IntTree other) {
IntTreeNode newRoot = this.helper(this.root, other.root);
return new IntTree(newRoot);
}
private IntTreeNode helper(IntTreeNode self, IntTreeNode other) {
if (other == null) {
// 'other' is null, copy the 'self' subtree
if (self == null) {
// Nothing to copy, return null
return null;
} else {
// Recurse down 'self'
return new IntTreeNode(
self.data,
this.helper(self.left, null),
this.helper(self.right, null));
}
} else if (self.left == null && self.right == null) {
// 'self' is a leaf node; do "remove matching" check
if (self.data == other.data) {
return null;
} else {
return new IntTreeNode(self.data);
}
} else {
// continue recursing
return new IntTreeNode(
self.data,
this.helper(self.left, other.left),
this.helper(self.right, other.right));
}
}Stylistically, this code doesn't seem very clean -- having this many if/else conditions and stuff feels a bit messy.
But again, in the final, we don't care about style, so it would be fine to stop here.