0

I'm having a bit of trouble understanding how Java is handling the following code. This is unfinished code to remove a node from a binary search tree. If I set a node to null (near the first print line), the node doesn't get set to null when I step out of recursion. But if I set the value of the node, the value does get set when I step out of recursion. Why does the behavior between the node and the node's value differ? I know this isn't the proper way to code a remove function, but I'm coding in this specific way as practice.

 /**
 * 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 deleteNode(TreeNode root, int key) {
        // Handles empty tree
        if (root == null) {
            return root;
        }
        // Current node has key
        else if (key == root.val) {
            // Node has no children
            if (root.left == null && root.right == null) {
                root.val = 50000;
                root = null;
                return null;
            }
        }
        // Left tree
        else if (key < root.val) {
            deleteNode(root.left, key);
            System.out.println(root.left.val);
            System.out.println(root.left);
        }
        // Right tree
        else if (key > root.val) {
            deleteNode(root.right, key);
        }
        return root;
    }
}

The input is:

[2,1,3]
1

This leads to a tree with 2 as the root, 1 as the left node, and 3 as the right node.

The output is:

50000
TreeNode@3f91beef
jphuong
  • 73
  • 6

1 Answers1

0

What you're doing here isn't actually overwriting the node as null. You're just taking the value of your variable, in this case root, and setting THAT to null. If you really want to remove the node, you need to make sure that its parent node doesn't reference it as its left or right subtree, and java garbage collection should automatically dispose of it.

Nathan
  • 56
  • 8
  • Could you further explain what setting the value of the variable to null means? How am I still able to change the member variable of the object the variable references to? – jphuong Jul 16 '22 at 07:46
  • @jphuong Let's say you have a variable x. Let's say we give the variable x the value of some arbitrary node y. Now, if we try to access the value attribute of y, x acts as a "pointer" and points us our Object y. So we can simply call x.value and it's functionally the same. When we set x to null, we aren't doing anything to y. We just change the Object it points to from the Object y to a null object. So y is effectively untouched, but if we try to access x then it points to null. – Nathan Jul 16 '22 at 08:45