Infinite loop while inserting nodes to BST

Question

I have a method to insert nodes in a BST according to the alphabetical order, but I have an infinite loop when I compare the 2 strings I think that the value never changes when it passes the comparison so it's comparing again with the same values resulting in an infinite loop. I think that the aux and Tnodes are not updating the values with the recursive method so it's comparing the same values over and over.

class BST {

    BSTNode root;

    public BST() {
        root = null;
    }

    BSTNode aux = new BSTNode();

    BSTNode insertNames(BSTNode T , int data, String name, double salary) {
        if (root == null) {
            T = new BSTNode();  
            T.setName(name);
            root = T;
        } else {
            aux = root;

            if (name.compareTo(aux.getName()) < 0)
                aux.setLeft(insertNames(aux.getLeft(),data, name, salary));
            else if (name.compareTo(aux.getName()) >= 0)
                aux.setRight(insertNames(aux.getRight(),data, name, salary));
        }

        return T;
    }    
}

class Main{
public static void main(String[] args){

        BST alpha=new BST();
        BSTNode root = new BSTNode();
        alpha.insertNames(root, 0, "Roy", 0);
        alpha.insertNames(root, 0, "Joseph", 0);
}
}

Possible duplicate of [How do I compare strings in Java?](http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java) — , May 13 '17 at 04:35
What did you find out when debugging the code line by line? That should show you why it has an infinite loop. — Sami Kuhmonen, May 13 '17 at 04:54
The values doesn't change but I can't find out why, when it gets to the first `if` inside the `else` sentence it inserts the value to the left of `aux` inside the recursive part when it comes again the parameter that is inside the method didn't change — Valenzuela, May 13 '17 at 05:03

score 0 · Answer 1 · answered May 13 '17 at 05:20

Please return the node in recursion end logic.

       /* If the tree is empty, return a new node */
if (root == null) {
    root = new BSTNode();
    root.setName(name);
    return root;
}

/* Otherwise, recur down the tree */
if (name.compareTo(root.getName()) < 0)
    root.setLeft(insertNames(root.getLeft(), data, name, salary));
else if (name.compareTo(aux.getName()) >= 0)
    root.setRight(insertNames(root.getRight(), data, name, salary));

/* return the (unchanged) node pointer */
return root;

or it can be solve iterative way

 if (localRoot == null) {
    newNode = new Node < V > (value, null);
    root = newNode;
    size++;
    return true;
}
if (comparator != null) {
//Some code
} else {
    Comparable << ? super V > v = (Comparable << ? super V > ) value;
    while (localRoot != null) {
        parent = localRoot;
        cmp = v.compareTo(localRoot.getValue());
        if (cmp < 0) {
            localRoot = localRoot.getLeftChield();
        } else if (cmp > 0) {
            localRoot = localRoot.getRightChield();
        } else {
            localRoot.incrementBy(nCopies);
            return true;
        }
    }
    newNode = new Node < V > (value, parent);
    if (cmp < 0) {
        parent.setLeftChield(newNode);
    } else if (cmp > 0) {
        parent.setRightChield(newNode);
    }
    size++;
    return true;
}
return false;

I tried the recursive way and I'm still getting the same stack overflow error produced by the infinite loop, I added my `main` class to the description, I'm pretty sure that the `root` parameter in `alpha.insertNames` is correct, I also checked the debugger and everything seems fine. — Valenzuela, May 13 '17 at 06:03
I debugged step by step and realized that the values never change, I'm comparing the same always so it does do what is inside the `if` sentence `root.setLeft` or `root.setRight` but the values don't change when it comes again so it's doing the same over and over again. — Valenzuela, May 13 '17 at 06:43
I have debug your code root your returning is different then root your checking. BSTNode T argument should check for recursion end condition. — gati sahu, May 13 '17 at 07:27

score 0 · Accepted Answer · answered May 13 '17 at 07:28

package com.gati.dsalgo.string;

class BST {

    BSTNode root;

    public BST() {
        root = null;
    }

    void insertNames(int data, String name, double salary) {
        root = insertNames(root, data, name, salary);
    }

    BSTNode insertNames(BSTNode root, int data, String name, double salary) {
        if (root == null) {
            root = new BSTNode();
            root.setName(name);
            return root;
        }

        if (name.compareTo(root.getName()) < 0)
            root.setLeft(insertNames(root.getLeft(), data, name, salary));
        else if (name.compareTo(root.getName()) >= 0)
            root.setRight(insertNames(root.getRight(), data, name, salary));

        return root;
    }
}

public class Main1 {
    public static void main(String[] args) {

        BST alpha = new BST();
        alpha.insertNames(0, "Roy", 0);
        alpha.insertNames(0, "Joseph", 0);
        System.out.println("hello");
    }
}

class BSTNode {
    private String name;
    BSTNode left;
    BSTNode right;

    public void setName(String name) {
        this.name = name;

    }

    public void setRight(BSTNode right) {
        this.right = right;
    }

    public void setLeft(BSTNode left) {
        this.left = left;
    }

    public BSTNode getRight() {

        return right;
    }

    public BSTNode getLeft() {
        return left;
    }

    public String getName() {

        return name;
    }

}

Infinite loop while inserting nodes to BST

2 Answers2