This is probably the right “intro to trees” question I’ve been looking for. The previous one I’ve been doing, “print everything in a binary tree”, is a bit too clunky. For those, people get hung up on the fixation with in-order versus pre-order or whatever, and also the problems usually model it as return an array of the visited nodes; and so they want to pass that as an out-parameter or similar. Ugh!

So I like this better.

def search(n: int, root: Optional[Node]) -> bool:
    """ Determines if a value is in a binary tree (NOT bst) """
    if root is None:
        return False
    if root.value == n:
        return True
    return search(n, root.left) or search(n, root.right)