Binary tree insertion problem.....insert() only putting new Nodes in the child of root nodes

Question

When I use insert() to inset new nodes into the binary tree it only inserts the new nodes on the place of child nodes even when root node already have left and right child. It is not visiting the child nodes to make deeper levels of binary tree.

Sorry for the bad English.

class Node
{
    int key;
    String value;
    Node lc = null;
    Node rc = null;

    Node(int k,String v)
    {   
        key = k;
        value = v;
    }

    public String toString()
    {
        return value + "is" + key;
    }
}

class BT
{
    Node root;
    public void insert(int k,String v)
    {
        Node newnode = new Node(k,v);

        if(root == null)
        {   
            System.out.println("root");
            root = newnode; 
            return;
        }

        Node n = root;
        while(n != null)
        {

            if(newnode.key <= n.key)
            { 
                n = n.lc;
                System.out.println("left");
                if(n==null){n = newnode; break;}
            }
            else
            { 
                n = n.rc;
                System.out.println("right");
                if(n==null){n = newnode; break;}
             } 

        }   
        System.out.println("loop ended");

        return;
    }


    }

    public class test
    {
    public static void main(String arg[])
    {
        BT list = new BT();

        list.insert(19,"one");
        list.insert(67,"sixtyseven");
        list.insert(5,"five");
        list.insert(12,"twelve");
        list.insert(67,"sixtyseven");

    }
}

Answer 1

What about using recursion? It's much more clear to realise.

public final class BinaryTree {

    private static final boolean ADD_TO_PARENT = true;
    private static final boolean ALREADY_ADDED = false; 

    private Node root;

    public void add(int key, String value) {
        Node node = new Node(key, value);

        if (add(node, root) == ADD_TO_PARENT)
            root = node;
    }

    private static boolean add(Node node, Node parent) {
        if (parent == null)
            return ADD_TO_PARENT;
        if (node.key <= parent.key) {
            if (add(node, parent.left) == ADD_TO_PARENT)
                parent.left = node;
        } else if (add(node, parent.right) == ADD_TO_PARENT)
            parent.right = node;

        return ALREADY_ADDED;
    }

    public static final class Node {

        private final int key;
        private final String value;
        private Node left;
        private Node right;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return value + " is " + key;
        }
    }

}

Answer 2

You never change the lc and rc links. Try something like this:

        if(newnode.key <= n.key)
        { 
            if(n.lc==null){n.lc = newnode; break;}
            n = n.lc;
            System.out.println("left");
        }
        else
        { 
            if(n.rc==null){n.rc = newnode; break;}
            n = n.rc;
            System.out.println("right");
         }