Modifying a class variable with a method within the class in Java

Question

The code below inserts new nodes in a Binary Search Tree.

When I'm creating an object of the class BinarySearchTree, in the driver function, and using its insert function for the first time, the root gets updated. This is how it should be too, since we are setting the root to be newNode.

But if we use the insert function of the same object thereafter, the root is not null anymore and only the currentNode variable within the function gets worked upon, after being set equal to root. The variable root of the object isn't being changed or worked upon, at all.

So why does the insert function, after its first use, is able to build the BST by adding nodes as the children of the root variable of the object?

public class BinarySearchTree {

    class BSTNode {

        public int value;
        public BSTNode left;
        public BSTNode right;
    }


    BSTNode root;

    BinarySearchTree () {
        root = null;
    }



    //Insert
    public void insert(int val) {

        BSTNode newNode = new BSTNode();
        newNode.value = val;

        if (root==null) {
            root = newNode;                //Root gets updated
            return;
        }

        BSTNode currentNode = root;        //currentNode will be worked upon

        while (true) {

            if (val <= currentNode.value) {

                if (currentNode.left==null) {
                    currentNode.left = newNode;
                    return;
                }

                currentNode = currentNode.left;
            }

            else {

                if (currentNode.right==null) {
                    currentNode.right = newNode;
                    return;
                }

                currentNode = currentNode.right;
            }
        }
    }

Answer 1

It may help to visualise what happens when a second value is inserted -- so in a tree that currently has one node, i.e. the root. Let's say we have this driver code:

BinarySearchTree tree = new BinarySearchTree();
tree.insert(5);
tree.insert(2);

At the start of the second insert execution, we have this situation:

tree
  ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │
│ root: ──────────────►│ left: null  │
└──────────────────┘   │ right: null │ 
                       └─────────────┘

First, newNode is created and given a value -- it has no dependency with the tree yet -- and currentNode is assigned the same reference as root:

tree                    currentNode       newNode
  ↓                       ↓                 ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │   │ val: 2      │
│ root: ──────────────►│ left: null  │   │ left: null  │
└──────────────────┘   │ right: null │   │ right: null │
                       └─────────────┘   └─────────────┘

Note how root and currentNode reference the same BSTNode instance, but also that these variables (root is a field), have their own memory for their references.

In the first iteration of the loop, this statement will be executed in the first if block:

currentNode.left = newNode;

Which mutates the single node that both currentNode and root reference. We get:

tree                    currentNode       newNode
  ↓                       ↓                 ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │   │ val: 2      │
│ root: ──────────────►│ left: ────────► │ left: null  │
└──────────────────┘   │ right: null │   │ right: null │
                       └─────────────┘   └─────────────┘

And in the next statement, currentNode will be reassigned a new reference -- following the one that was assigned to the left field, and so we get:

tree                                  currentNode  newNode
  ↓                                        ↓         ↓
┌─BinarySearchTree─┐   ┌─BSTNode─────┐   ┌─BSTNode─────┐
│                  │   │ val: 5      │   │ val: 2      │
│ root: ──────────────►│ left: ────────► │ left: null  │
└──────────────────┘   │ right: null │   │ right: null │
                       └─────────────┘   └─────────────┘

Note that an assignment to a variable (not a field), will never mutate an object. It just affects that variable itself.

Hope this clarifies it.