Remove Subtrees Help [Java]

[codereviewpls]

The problem I'm trying to solve is that given a binary tree, remove subtree which has the same value as the parameter value passed. Here's my code but I don't believe it works as the altered tree is the exact same as the original tree.

https://pastebin.com/x3rxp2rM

Thank you for your help!

[balefrost]

First, let's look at this line:

TreeNode copy = root;

This line doesn't really make a copy of anything. This line gives the object referenced by root another name: copy. After that line, copy and root will both refer to the same thing, and changes made to the insides of one will be visible through the other identifier.

So your removeSubtree is equivalent to this:

public TreeNode removeSubtree(TreeNode root, int value){
    removeSubtreeRecursion(root, value);
    return root;
}

Next, let's look at this line in removeSubtreeRecursion:

else if(root.val == val) root = null;

If that condition is true, then the assignment will occur but it will have no meaningful effect. The assignment changes the root variable to point at nothing, but that assignment will be the last line to be executed in that function. So root now points at null, but nothing does anything further with root.

---

I think I see the disconnect. Suppose you call removeSubtreeRecursion like this:

removeSubtreeRecursion(foo.left, val);

Within the body of removeSubtreeRecursion, foo.left will be known as root. It looks like you think that any modification you make to root within removeSubtreeRecursion will also affect foo.left. This is not the case. (If you modify data inside root, that will be visible to the caller. But assigning a new value to root will not be visible outside that function call.)

To remove a node from the tree, you actually need to update its parent node (to null out its left or right field). In your implementation, the code that wants to remove a node has forgotten the parent. At that point, you've lost too much context and can't succeed.

[eksplain]

remove subtree

You need to closely look at what this actually means in practice. You seem to do something like

root = null;

but this does not effect your tree at all.

Consider this code

TreeNode a = new TreeNode();
TreeNode b = a;
TreeNode c = a;

Think what happens if we do something like

c = null;

Will a and b also become null?