Part of the problem is that you’re not following good OO principles.

In this case, the one that’s probably most applicable is “Tell, don’t ask“: If you want a Node to add a child, you should tell it to add a child, you shouldn’t ask it to expose all the relevant information you need then go ahead and add the child for it. Likewise, if (because you’re doing an iterative solution), you need to traverse a level down the tree, tell the Node you want to traverse to the appropriate child, don’t ask it for everything you need to know to do the calculation yourself.

Consider:

private class Node {
    int key;
    int val;
    Node left = null;
    Node right = null;
    Node (int k, int v) {
        key = k; val = v;
    }

   public Node traverseNext(int targetKey) {
       if (key==target) {
           return null;
       }
       return key < target ? left : right;
   }

   public void setChild(int key, int value) {
       if (key == this.key) {
           return;
       }
       if (key < this.key) {
           left = new Node(key, value);
       }
       else {
           right = new Node(key, value);
       }
   }

Then a caller wanting to add a child would just have to do:

Node node;
Node nextNode = root;

while(nextNode != null) {
    node = next;
    nextNode = node.traverseNext(key);
}

node.setChild(key, value);

(Excuse any mistakes, Java isn’t my native language)

That’s not exactly stellar code because I had to go out of my way to work around the obvious recursive solution. For example, you wouldn’t realistically want to expose a method that cheerfully replaces one child with another if asked. But it should give the basic idea.

Note: I realise that this doesn’t very directly address the issue which caused the difference between those two code samples- the capability that a pointer has which a reference doesn’t. But I’m also of the opinion that it’s no coincidence that as soon as you solve this problem in a Java-idiomatic way, that difference ceases to be relevant.

You can avoid the repetition by creating the new child Nodes earlier and defaulting them to empty, rather than using null to represent an empty Node. The body of your while loop might look something like:

Node child = node.right;
if (k < node.key)
    child = node.left;
if (child.isEmpty()) {
    child.set(k, v);
    child.left  = new Node();  //Could be done inside set
    child.right = new Node();
    return;
} else {
    node = child;
}

This basically preallocates the next level of leaves, but shouldn’t be too much overhead. Another option could be replacing left and right with a children[2], then you can use the array index to avoid the repetition.

There is no way to do what you want to do in Java. Java doesn’t offer the freedom of C when dealing with pointers. The only pointers Java has are object references.

Your first attempt is therefore as good as you can do in Java. You have to distinguish the case of left, right and root insertion. If creating and initializing the node is complex, you can move the node creation code to a procedure.

Adding a Link object is a clever idea but it complexifies the data structure as you noted. It also affects all other methods that manipulate or traverse the tree, and that just to make your insert method more elegant. A bit silly if you think of it.

So the answer is you can’t. This being said, I am sure it is just an exercise, so experiment as you like. But in real life, before writing your own binary sort tree, make sure no Java collection fills your needs. And if they don’t, check out open source frameworks like Google guava.

Ben Aaronson’s answer is much better than either of my attempts, but I think the main reason is the technique he uses to iterate through the tree, using two Node pointers instead of one, rather than the more object-orientated style. The whole thing can be inlined, which allows a direct comparison with my version and shows that it is indeed more elegant, cleanly separating the tree traversal from the node creation (even if it does still take twice as much code as the C++ version):

void insert(int k, int v) {
    if (root == null) {
        root = new Node(k, v);
        return;
    }

    Node node = root;
    Node next = root;

    while (next != null) {
        node = next;
        if (k == node.key) 
            next = null;
        else
            next = k < node.key ? node.left : node.right;
    }

    if (k == node.key)
        node.val = v;
    else if (k < node.key)
        node.left = new Node(k, v);
    else if (k > node.key)
        node.right = new Node(k, v);
}

I do take on board Ben’s broader points about the value of using OO principles, and clearly the code is improved further by dividing it into separate methods as he has done.