Search code examples
javabinary-search-treeinsertion

how to make this binary search tree work??? (in Java)


public void insert(int data) {
        if (root == null) root = new AVLNode(data);
        else {
            AVLNode node = root;
            while (node != null) {
                if (node.data <= data) {
                    node = node.right;
                }
                else {
                    node = node.left;
                }
            }
            node = new AVLNode(data);
        }
    }

im trying to make a binary search tree (nonrecursive) and then later on access is and do a preorder traversal, but when i print root i only get 1 element. all the insertions work, i think, but then root just has the first insertion in it and its left and right dont refer to anything, i think thats why im only getting 1 element. how do i refer root to the top of the node tree? here is the node class btw

class AVLNode
{
    AVLNode left, right;
    int data;

    /* Constructor */
    public AVLNode()
    {
        left = null;
        right = null;
        data = 0;
    }
    /* Constructor */
    public AVLNode(int n)
    {
        left = null;
        right = null;
        data = n;
    }
}

Solution

  • The problem is on the reference of variables. While loops until reaching a null value on node variable and then you assign the new node to it. But there is no link between the parent node.left or node.right and the new node variable because it has a null value assigned. So you are assigning the value to a variable not linked to anything and it will be lost. You need to assign new nodes directly to the node.left or node.right like this example:

    public void insert(int data) {
       if (root == null) {
          root = new AVLNode(data);
       } else {
          AVLNode node = root;
          AVLNode newNode = new AVLNode(data);
          while (node != null) {
             if (node.data <= data) {
                if (node.right == null) {
                   node.right = newNode;
                   node = null;
                } else {
                   node = node.right;
                }
             } else {
                if (node.left == null) {
                   node.left = newNode;
                   node = null;
                } else {
                   node = node.left;
                }
             }
          }
       }
    }