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");

    }
}

`n = n.lc;` and then `n = newnode` does not do what you think it does. Just do `n.lc = newnode` and just do `n = n.lc` when you need to go on, not when you found the node. Same for `n.rc` of course. — Federico klez Culloca, Aug 27 '19 at 13:16
See [here](https://stackoverflow.com/questions/26789940/java-object-assignment-behaviour-not-consistent?noredirect=1&lq=1) for a different take on the problem. — Federico klez Culloca, Aug 27 '19 at 13:20

score 1 · Accepted Answer · answered Aug 27 '19 at 13:18

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");
         }

score 0 · Answer 2 · answered Aug 27 '19 at 13:24

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;
        }
    }

}

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

2 Answers2