So my binary search tree doesn't seem to be traversing through all the nodes. each node has references to other nodes. So I'm traversing through right or left (depending on value) until I hit null, which means I can insert. After insertion, I reset root to first so it can reiterate through the top of the search tree when I call it next. But instead, it's not working as it should, seems like it only moves through the first node.
My constructor for the BST:
public BST() {
root = null;
first = null;
size = 0;
}Constructor for node:
protected Node(K key, V value) {
if ((key == null) || (value == null)) {
throw new NullPointerException();
} else {
this.key = key;
this.value = value;
left = null;
right = null;
parent = null;
predecessor = null;
successor = null;
};This is the method for insert:
public V put (K key, V value) {
if (root == null) {
root = new Node(key, value);
if (size == 0) {
System.out.println("Setting first root!");
first = root;
}
size++;
System.out.println("Inserted " + root.key);
root = first;
System.out.println(size);
return root.value;
}
else {
int compareKeyToNode = key.compareTo(root.key);
// Compares key to root's key, returns -1 if less than, 1 if greater than, 0 if keys are equal
if (compareKeyToNode > 0) {
System.out.println("Moved right of " + root.key);
root = root.right;
}
if (compareKeyToNode < 0) {
System.out.println("Moved left of " + root.key);
root = root.left;
}
}
return (put(key, value));
}Say for input of 15, 12, 14, 8
It should print:
Inserting 15
Moving left of 15
Inserting 12
Moving left of 15
Moving right of 12
Inserting 14
Moving left of 15
Moving left of 12
Inserting 8
Instead, it outputs:
Inserting 15
Moving left of 15
Inserting 12
Moving left of 15
Inserting 14
Moving left of 15
Inserting 8
So it only seems to be traversing through the top node and inserts right away even though it shouldn't be null. Can anyone spot a logic error in my code?