Breadth First Search

breadth_first_search.js

//Assumes: 
//a Queue data structure is available with push(), pop(), isEmpty() methods.
//each node in the Queue have left and right properties.

//Time Complexity: O(N)
//Space Complexity: O(N)
const bfs = (root, value) => {
  let q = new Queue();
  
  q.push(root);
  
  while(!q.isEmpty()) {
    let n = q.pop();
    if(n.value === value){
      return n;
    } else {
      if(n.left) {
        q.push(n.left);
      }
      if(n.right) {
        q.push(n.right);
      }
    }
  }
}