Tree Search: Depth-First

The best-case complexity is O(log n), while the worst case is O(n), which depends on the balance.

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

function search(
  cur: BinaryNode<number> | null, 
  pointer: number
): boolean {
  if (!cur) {
    return false
  }

  if (cur.value === pointer) {
    return true
  }

  if (cur.value < pointer) {
    return search(cur.right, pointer)
  }

  return search(cur.left, pointer)
}

function depthFirstSearch(
  head: BinaryNode<number>, 
  pointer: number
): boolean {
  return search(head, pointer)
}