Java binary search tree - incorrectly working insert method

Question

I've a binary search tree homework in Java where I was given complete Tree and Node classes and a SearchTree class in which I'm to complete the search and insert methods. The search is supposed to return the value of the node corresponding the searched key.

Here is the Tree class and here the Node class. My search and insert methods are below.

It seems I'm getting close, but test insert of key 0 and value 2 into Tree[Node[0,1,null,null]] results in Tree[Node[0,1,null,null] rather than the correct Tree[Node[0,2,null,null]]. What am I not understanding here?

public static Object search(Tree tree, int key) {
    Node x = tree.getRoot();
    while (x != null) {
        if (key == x.getKey()) {
            return x.getValue();
        }
        if (key < x.getKey()) {
            x = x.getLeft();
        } else {
            x = x.getRight();
        }            
    }
    return null;
}

public static void insert(Tree tree, int key, Object value) {
    if (tree.getRoot() == null) {
        tree.setRoot(new Node(key, value));
    }
    Node juuri = tree.getRoot();
    while (juuri != null) {
        if (key == juuri.getKey()) {
            return;
        } else if (key < juuri.getKey()) {
            if (juuri.getLeft() == null) {
                juuri.setLeft(new Node(key, value));
                return;
            } else {
                juuri = juuri.getLeft();
            }
        } else {
            if (juuri.getRight() == null) {
                juuri.setRight(new Node(key, value));
                return;
            } else {
                juuri = juuri.getRight();
            }
        }
    }
}

Robert Prior Robert Prior · Accepted Answer · 2013-02-18T17:32:08

Well the issue I am seeing is that key values in your tree are unique. In this if statement you leave your insert method without adding a node if you see that the key is already in the tree.

 if (key == juuri.getKey()) { 
      return;
 }

In your example (if I understand it right) 0 is already in the tree so nothing changes when inserting 0 again. Based on your example, I am assuming you want to do an update on a node if the key is the same. So this code would do it.

if (key == juuri.getKey()) {
     juuri.setValue(value);
     return;
}

Java binary search tree - incorrectly working insert method

1 Answers