Remove Subtree with specific value

Question

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);
    }
}

your tree stays the same because you update the subtree pointers passed as arguments instead of original ones. your methods should return the updated pointers to subtrees, which in turn should be assigned to the pointers in the caller method — mangusta, Nov 30 '18 at 05:58

Yola · Accepted Answer · 2018-11-30T18:06:40.917

0

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.

edited Nov 30 '18 at 18:06

answered Nov 30 '18 at 06:11

Yola

18,496
11
65
106

The removeSubtree method is returning removeSubtreeRecursion which doesn't return anything however. I am trying to return the root node. I believe it would be better to call removeSubtreeRecursion then return root. – codernoob Nov 30 '18 at 16:38
@codernoob you are completely right. And thank you for a nice question. – Yola Nov 30 '18 at 18:05

Remove Subtree with specific value

1 Answers1

Linked