javascriptrecursionbinary-treeinsertion

Error in Recursive Function Used For Inserting a Node in a Binary Tree in JavaScript


I am getting undefined after the node is inserted in the tree, don't know why is that happening. Here's what is happening - after the node is inserted, the function should return true, but it instead returns undefined. After inserting the node, the code doesn't stop and goes back to if check condition, sets 'current' to '7', this keeps happening until 'current' is '10'(root value) and then it finally goes back to insert() function which returns undefined. My only problem is that why is it returning undefined, and why is it going back to root after inserting the node in the desired place. Can someone please tell me? Am I missing something very small?

by the way, the value I inserted is 8. tree.insert(8);

class Node{
    constructor(val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree{
    constructor(){
        this.root = null;
    }

    insert(val){
        if(!this.root){
          this.root = newNode;
          return this;
        }
        let newNode = new Node(val);
        if(val === this.root.val)return false;
     
        function recursiveInsert(current,newNode){ 
            if(newNode.val === current.val)return false;      

            if(newNode.val > current.val){
              if(!current.right){
                  current.right = newNode;             
                  return true;
              }           
              recursiveInsert(current.right,newNode);
            }

            if(newNode.val<current.val){   
              if(!current.left){
                  current.left = newNode;              
                  return true;
            }
            recursiveInsert(current.left, newNode);
          }        
       }    
      return recursiveInsert(this.root,newNode);                         
    }
  }

let tree = new BinarySearchTree();

tree.root = new Node(10);
tree.root.left = new Node(7);
tree.root.right = new Node(15);
tree.root.left.right = new Node(9);

Solution

  • You should return the recursiveCall or you will get undefined because the recursive call take time to execute and the function won't wait for it to return something.

    // ...code
    return recursiveInsert(current.right,newNode);
    // and
    return recursiveInsert(current.left,newNode);