I cannot set the root of the tree to null?

Question

I was trying to solve this problem on leetcode, by seeing what i have written i think my logic is correct but i am getting the same tree in return as output which is wrong. I had a doubt can i not set the current scope of root of tree to null ? after seeing the solutions of people they have made the root.left null or root.right null not the root itself like mine. Am i missing some basic concept here.
Link to the LeetCode problem :- https://leetcode.com/problems/binary-tree-pruning/
My solution :-

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        cleanTree(root);
        return root;
    }
    
    public boolean cleanTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean left = cleanTree(root.left);
        boolean right = cleanTree(root.right);
        if(root.val == 0 && left  && right) {
            root = null;
            return true;
        }
        
        return false;
    }
}

*"I had a doubt can i not set the root of tree to null"* Since you're not asked to do that, why is that a concern? The assignment is to "return the same tree where every **subtree** (of the given tree) not containing a 1 has been removed". Since you're only removing sub-trees, the **root node will always remain**. — Andreas, Sep 17 '20 at 04:46
The fact that you named the `cleanTree()` parameter **`root`** is confusing, because most of the time, the value isn't the root of the tree. The parameter to `pruneTree()` is "the root of the tree". The parameter to `cleanTree()` is just some node. --- You should never null out the node itself, you null out the `left` and `right` references, then return `true` if you want the *caller* to null out the reference to the node. — Andreas, Sep 17 '20 at 05:41
So you are asking why `root = null` doesn't null out the `root.left` or `root.right` in the caller. The answer is here: [Is Java “pass-by-reference” or “pass-by-value”?](https://stackoverflow.com/q/40480/5221149). — Andreas, Sep 17 '20 at 05:51
@Andreas Thanks you now I got clearly understooded where i had been wrong. You exactly cleared what i had doubt in the how the things are passed — chickenmomosTarriwale, Sep 17 '20 at 06:10

ViciousCupcake · Answer 1 · 2020-09-17T07:34:57.627

0

They set root.left or root.right to null because they can't set the current node root to null.

Setting root to null as you did inside the if statement only sets the memory address of root to null within the scope of the current method. The pruneTree method would not see root becoming null.

Side note, the root node is not guaranteed to be non-null. e.g. with the tree

 0 <--root
0 0

, the root would be null

edited Sep 17 '20 at 07:34

answered Sep 17 '20 at 05:08

ViciousCupcake

1
1

Since the assignment is to "return the same tree where every **subtree** (of the given tree) not containing a 1 has been removed". Only the subtrees are nulled out, the root always remains and will never be set to null. Second half of answer is wrong. – Andreas Sep 17 '20 at 05:45
1

This question is definitely vague, but I coded this exact problem yesterday with the assumption that a tree of all zeros has root null, and it worked on every test case, not to mention that the solution on the lc website did the same thing as I – ViciousCupcake Sep 17 '20 at 07:32

Joop Eggen · Answer 2 · 2020-09-17T08:05:25.910

The problem is that in java variables passed to a method will never be assigned to by the method itself. This was introduced to prevent evil calls unexpectedly modifying passed variables. [Code Quality]

Hence setting a variable involves assigning the call's return value to the variable.

public TreeNode pruneTree(TreeNode root) {
    root = cleanTree(root);
    return root;
}

public TreeNode cleanTree(TreeNode node) {
    if (node == null) {
        return node;
    }
    node.left = cleanTree(root.left);
    node.right = cleanTree(root.right);
    if (node.val == 0) {
        if (node.left == null) {
            return node.right;
        }
        if (node.right == null) {
            return node.left;
        }
        // Bad luck ... should delete node.
    }
    return node;
}

Here the boolean result is not needed. In the simplest case the passed TreeNode is returned.

(For clarity I wrote root = cleanTree(root);.)

Deleting a node in the middle

public TreeNode cleanTree(TreeNode node) {
    if (node == null) {
        return node;
    }
    node.left = cleanTree(root.left);
    node.right = cleanTree(root.right);
    if (node.val == 0) {
        if (node.left == null) {
            return node.right;
        }
        if (node.right == null) {
            return node.left;
        }

The if's above now are just a heuristic optimisation, doing often less work.

        // Delete node in the middle:
        // - either node.left as node.right's left-most leaf's left,
        // - or node.right as node.left's right-most leaf's right.
        // Sometimes called a pointer rotation (for 3 positions).
        if (depth(node.left) < depth(node.right) {
            TreeNode rightMin = node.right;
            while (rightMin.left != null) {
                rightMin = rightMin.left;
            }
            rightMin.left = node.left;
            return node.right;
        } else {
            TreeNode leftMax = node.left;
            while (leftMax.left != null) {
                leftMax = leftMax.right;
            }
            leftMax.right = node.right;
            return node.left;
        }            
    }
    return node;
}

private int depth(TreeNode node) {
    return node == null ? 0
             : 1 + Math.max(depth(node.left), depth(node.right);
}

I cannot set the root of the tree to null?

2 Answers2