javaalgorithmtreebinary-treesubtree

Remove Subtree with specific value


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.

Before:
              5
            /   \
          3       2
         / \     / \
        2   1   4   3

After removal of subtree of value 2:
              5
            /
           3      
            \    
             1  

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

public void removeSubtreeRecursion(TreeNode root, int val){
    if(root == null) return;
    else if(root.val == val) root = null;
    else{
        removeSubtreeRecursion(root.left, val);
        removeSubtreeRecursion(root.right, val);
    }
}

Solution

  • You can use parent node instead of current node to be able to modify it. It could be something like this:

    public TreeNode removeSubtree(TreeNode root, int value){
        if (root != null && root.val == value) return null;
        removeSubtreeRecursion(root, value);
        return root;
    }
    
    public void removeSubtreeRecursion(TreeNode parent, int val) {
        if (parent.left != null && parent.left.val == val) parent.left = null;
        else removeSubtreeRecursion(parent.left, val);
        if (parent.right != null && parent.right.val == val) parent.right = null;
        else removeSubtreeRecursion(parent.right, val); 
    }
    

    In your implementation root = null modifies local reference. You can read more about this in Pass by reference in Java.