Insert node recursively

Question

I am trying to insert node in a binary tree using recursive method. But once its out of the method the root becomes the new node and left child and right child are null. With this I'm trying to learn how recursion works. Also, does recursive method always has to return something. Below is the code.

public class BinaryNode {
     int key;
     BinaryNode left;
     BinaryNode right;

    public BinaryNode( int key){
        this.key = key;
       // this.left = left;
        //this.right = right;

    }
}

public class BinaryTree {

    BinaryNode root;


    public  void insert(int key){

        BinaryNode newNode = new BinaryNode(key);

            if(root == null){
                root = newNode;

            }else{
                  BinaryNode focusNode = root;
                  BinaryNode parent;

                while(true){
                    parent = focusNode;
                    if(key<focusNode.key){

                        focusNode = focusNode.left;
                        if(focusNode==null){
                            parent.left= newNode;
                            return;
                        }

                    }else{
                        focusNode = focusNode.right;
                        if(focusNode==null){
                            parent.right= newNode;
                            return;
                        }
                    }

                }

            }





    }

    public BinaryNode recursiveInsert(int key, BinaryNode node){
        BinaryNode newNode = new BinaryNode(key);
        if (node == null){
            root = newNode;

        }

        else{

            if(key < node.key){


                 root.left = recursiveInsert(key, node.left);


            }
            else{

                 root.right = recursiveInsert(key, node.right);


            }
        }

      return root;
    }




     public String toString(){
         String toTree = null;



        return toTree;
     }

    public static void main(String[]args){
        BinaryTree tree = new BinaryTree();

        tree.recursiveInsert(7, tree.root);
        tree.recursiveInsert(6, tree.root);
        tree.recursiveInsert(4, tree.root);
        tree.recursiveInsert(8, tree.root);
        tree.recursiveInsert(9, tree.root);
        tree.recursiveInsert(5, tree.root);



    }

}

The method I'm trying is recursiveInsert. Thanks!!

Answer 1

I suppose the problem comes from

if (node == null){
        root = newNode;
}

You are traversing the tree and in the last step you are asking the left/right child of a leaf node. This hasn't one, so it's child is null. This is the value returned by the recursive calls and in the end, it gets assigned to root.

To fix this, before descending into a node, make sure that child node exists.

Also this is a bit weird

root.left = recursiveInsert(key, node.left);

It should be node and not root.

Answer 2

Your recursive code should be like this :

public BinaryNode recursiveInsert(int key, BinaryNode node) {
    if (node == null) {
        return root = new BinaryNode<>(key);
    } else {
        if (key < node.key) {
            if (node.left == null) {
                return node.left = newNode;
            } else {
                return recursiveInsert(key, node.left);
            }
        } else {
            if (node.right == null) {
                return node.right = newNode;
            } else {
                return recursiveInsert(key, node.right);
            }
        }
    }
}

You are acting on root node in your recursive function, you should rather be acting on the node passed to the recursive function.

Answer 3

There are several issues with your code which I won't necessarily go into, because I think they distract from your core questions.

To answer your second question first: No, there's no rule that says that recursive methods have to return anything. It's more important that they know when to terminate.

As for your bug, I think it's probably due to the fact that your insert method always returns and operates on root. You probably mean to modify and return newNode.

Answer 4

This is because your recursiveInsert method always operates on root. Try this instead -

public Node recursiveInsert(Node currentParent, Node newNode) {

        if (currentParent == null) {
            return newNode;
        } else if (newNode.key > currentParent.key) {
            currentParent.right = recursiveInsert(currentParent.right, newNode);
        } else if (newNode.key < currentParent.key) {
            currentParent.left = recursiveInsert(currentParent.left, newNode);
        }

        return currentParent;
    }