0

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?

1
Contributor
1
Reply
4
Views
7 Years
Discussion Span
Last Post by iamsmooth
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.