Tree Search: Breadth-First

Initially, the complexity is O(n), but when implemented in JavaScript, the complexity becomes O(n²) due to the usage of get, pop, and push operations.

type BinaryNode<T> = {
  value: T
  left: BinaryNode<T> | null
  right: BinaryNode<T> | null
}

function breadthFirstSearch(
  head: BinaryNode<number>, 
  pointer: number
): boolean {
  
  const q: (BinaryNode<number> | null)[] = [head]

  while (q.length) {
    const cur = q.shift() as BinaryNode<number> | undefined | null

    if (!cur) {
      continue
    }

    // search
    if (cur?.value === pointer) {
      return true
    }
    
    if (cur.left) {
      q.push(cur.left)
    }

    if (cur.right) {
      q.push(cur.right)
    }
  }

  return false
}