CODEWITHSUNDEEP
javadata-structuresbinary-search-tree
user2916610
user2916610

Reputation: 765

What is the difference between these two implementation of insertion operation to BST?

There is the code:

public class BST {
    public Node root;

    private class Node {
        int key;
        String value;
        int N;
        Node left, right;

        public Node(int k, String v, int n) {
            key = k;
            value = v;
            N = n;
        }
    }

    public String get(int key) {
        return get(root, key);
    }

    private String get(Node n, int k) {
        if(n == null) {
            return null;
        }
        if(k == n.key) {
            return n.value;
        } else {
            if(k < n.key) {
                return get(n.left, k);
            } else {
                return get(n.right, k);
            }
        }
    }

    //    This snippet puzzles me
    public void put(int key, String value) {
        root = put(root, key, value);
    }

    private Node put(Node n, int k, String v) {
        if(n == null) {
            return new Node(k, v, 1);
        }
        if(n.key == k) {
            n.value = v;
        } else {
            if(k < n.key) {
                n.left = put(n.left, k, v);
            } else {
                n.right = put(n.right, k, v);
            }
        }
        n.N = size(n.left) + size(n.right);
        return n;
    }
    //    snippet ends


    public static void main(String[] args) {
        BST r = new BST();
        r.put(2, "root");
        r.put(1, "left");
        r.put(3, "right");

        System.out.println(r.get(2));
        System.out.println(r.get(1));
        System.out.println(r.get(3));
    }


}

output:

root
left
right

It works just fine:)

However, when I change the put method like this:

    public void put(int key, String value) {
        put(root, key, value);
    }

    private void put(Node n, int k, String v) {
        if(n == null) {
            n = new Node(k, v, 1);
        }
        if(n.key == k) {
            n.value = v;
        } else {
            if(k < n.key) {
                put(n.left, k, v);
            } else {
                put(n.right, k, v);
            }
        }
        n.N = size(n.left) + size(n.right);
    }

I got the output

null
null
null

Obviously, the new put method failed. But why? In my opinion, these two different implementations are just not much different.

Upvotes: 0

Views: 75

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533482

In Java, when you read Node n the n is a local copy of a reference. When you assign this local copy it doesn't change the copy in the caller. ie.

private void put(Node n, int k, String v) {
    if(n == null) {
        n = new Node(k, v, 1); // this doesn't change the caller.
    }

if you don't return the node to assign to the root, n.left or the n.right, you are creating a node, but you are not adding it to the tree.

If you want to investigate this further I suggest you step through the code in your debugger and you will be able to see what each line of code is doing.

Upvotes: 1

Matteo Di Napoli
Matteo Di Napoli

Reputation: 577

When you change the assignment 

n.left = put(n.left, k, v);

to

put(n.left, k, v);

(or the same with the n.right), and you don't already have a node there, you're assigning a new node to n variable, but you're not updating the link from the parent to the child at the return from the recursive call. So the new Node will remain isolate beacuse you're changing the reference of n inside your last recursive call but not n.left(or right) parent's reference. Moreover, I guess that when the value of reference n will be discharged at the end of last recursive call, since no other reference is pointing to the newly created node, this would be eventually eliminated by the garbage collector.

Upvotes: 1

Related Questions