CODEWITHSUNDEEP
javascriptbinary-tree
Mugs
Mugs

Reputation: 339

Why am I getting an infinite loop while trying to search my Binary Tree?

I inserted numbers into the tree. I use get to see if that number exists(knowing it does) and google chrome crashes because its looping infinitely. I've gone over the code multiple times and I can't figure out why its not working. Please help.

My commands in console:

 tree = new BinaryTree;

 tree.insert(15);
 tree.insert(23);
 tree.insert(6);

etc...

 tree.get(55);

Google Chrome CRASHES NOOOOOO collapses

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

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

    insert(val){
        var newNode = new Node(val);
        if (this.root){
            var current = this.root
            while(true) {
            if(val < current.val){
                if(current.left === null){
                    current.left = newNode;
                    return current;
                }
                current = current.left;
            }
            if(val > current.val){
                if(current.right === null){
                    current.right = newNode;
                    return current; 
                }
                current = current.right;
            }
            if(val === current.val){
                return "already exists";
            }
        }
    }
    this.root = newNode;
    return this;
}

    get(val) {

        if(this.root){
            var current = this.root;
            while(true){
                if (val < current.val){
                    if(current.left == null){
                        return "does not exist";
                    }
                    current = current.left;
                }
                if (val > current.val){
                    if(current.right == null){
                        return "does not exist";
                    }
                    current = current.right;
                }
                 if(current === val){
                        return current;
               } 
            }
        }
        return "tree is empty";
    }
}

Upvotes: 1

Views: 256

Answers (2)

Gabor Szekely
Gabor Szekely

Reputation: 1238

Your code is fine, you are simple doing the equality check wrong at the bottom of the get() method. You are checking the node object itself for equality to the passed in value instead of it's .val property.

You wrote:

if(current === val){
    return current;
}

When it needs to be:

if(current.val === val){
    return current;
}

Upvotes: 1

Nsoseka
Nsoseka

Reputation: 319

Your code never breaks out of this while loop

 while(true) {
   if(val < current.val){
      if(current.left === null){
         current.left = newNode;
         return current;
       }
      current = current.left;
   }
 }

white(true) will always be true, so that runs infinitely if you don't return out of the loop, so my guess is that for some reason current.left === null is never true

Upvotes: 0

Related Questions