insertion in binary node tree using recursion

Question

Below is my code. I'm trying to return head node back after I insert value to either left or right node. I understood the concept of insertion, but I'm unable to understand how can I return my head node back to that now it is back to original state with addition node added. Here is exactly I don't understand.

When I insert my node how can I break the loop and return its head node back.
Recursion is stack concept which will output based on LIFO and if it is lifo how can I have head node returned back

Here's my code:

   class Node {
            int data;
            Node left;
            Node right;
            }


        static Node Insert(Node root,int value) 
        {

            return nodeHelper(root,value); 

        }

        static Node nodeHelper(Node root,int value){
            Node nodeTracker = root; 
            Node temp; 
            if(root!=null){

                if(value>root.data){
                    if(root.right==null){
                        temp =new Node(); 
                        temp.data = value; 
                        root.right = temp; 
                        return nodeTracker; 
                    }
                   else{
                       nodeHelper(root.right,value); 
                   }

                }

                else{
                    if(root.left==null){
                        temp=new Node(); 
                        temp.data = value; 
                        root.left = temp; 
                        return nodeTracker; 
                    }

                    else{
                        nodeHelper(root.left,value); 
                    }
                }
            }

            else{
                temp=new Node(); 
                temp.data = value; 
                return temp; 
            }

        }
        }

The nodeHelper is going to insert the new node at the right place. You have the root available in the Insert method. Why can't you just return the root from the Insert method. static Node Insert(Node root,int value) { nodeHelper(root,value); return root; } — raghu
– raghu, Commented Nov 20, 2017 at 6:17

Jim Mischel · Accepted Answer · 2017-11-20 04:18:41Z

0

To return the root of the tree, you need a third parameter that you pass around to keep track of the root. Like this:

Node* nodeHelper(Node* nodeTracker, Node* parent, int value)

Remove the local nodeTracker variable.

Your recursive calls become:

return nodeHelper(nodeTracker, parent.left, value);

(and, of course, same thing for the right branch)

And your initial call in the insert function is:

return nodeHelper(root, root, value);

edited Nov 20, 2017 at 4:18

answered Nov 20, 2017 at 3:34

Jim Mischel

135k25 gold badges197 silver badges377 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Kay Over a year ago

Jim, thanks for the comment. Let us say I'm passing values 1,2,3,4,5,6 and my head node lets say is 4. When I add new value 7 to the list, then how can I return this head node back to the method where I call this. Also, I have return values in the program where I'm returning temp value. Just want to be sure if you saw that. I'm trying to understand what should be the base case for my logic/ concept. Thanks.

Kay Over a year ago

Here is the link. There could be many ways, but I really appreciate how to use my logic for this case as I'm having tough time understanding recursion concept. hackerrank.com/challenges/binary-search-tree-insertion/problem

Kay Over a year ago

Thanks Jim. This is very useful. I appreciate your feeback and comments.

Collectives™ on Stack Overflow

insertion in binary node tree using recursion

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related