 Given the root of a balanced BST `root`, and a target value `target`, return whether the tree contains the target value. Example: Explanation: The tree contains a node with the target value 3, so we return True. The solution is just to apply Binary Search to the BST. Whenever `target` is smaller than the current value, we go left. And whenever `target` is larger than the current value, we go right. For example, searching for the number 3 looks like this: s1 `` hasTarget(node) returns whether tr

Search a BST


-----problem-----
    Given the root of a balanced BST `root`, and a target value `target`, return whether the tree contains the target value.

\b{Example:}  




\image{0}
$$
\begin{align*}
&\large \texttt{target = 3} \\[4bp]
&\large \texttt{=> returns True}
\end{align*}
$$

\b{Explanation:}
The tree contains a node with the target value 3, so we return True.


-----solution-----

The solution is just to apply Binary Search to the BST. Whenever `target` is smaller than the current value, we go left. And whenever `target` is larger than the current value, we go right. For example, searching for the number 3 looks like this:

\image{bs.png}



\s1


``
hasTarget(node) # returns whether tree has `target`
``

\s2

``
hasTarget(node) = (
    if target == node.val: return True
    if target < node.val:  return hasTarget(node.left)
    if target > node.val:  return hasTarget(node.right)
)
``

\s3

If we get to a node that's None, then we know the target is not in that tree.

``
hasTarget(None) = False
``

\s4

\answer

\tc $O(\log n)$

\sc $O(\log n)$ for the Call Stack.


You can easily make this iterative:
```
def binarySearchTreeHasTarget(root, target):
    node = root

    while True:
        # base case
        if node is None:
            return False
        # recursion
        if target == node.val: return True
        if target < node.val:  node = node.left
        else:                  node = node.right
```
\tc $O(\log n)$

\sc $O(1)$





Recursion

Search a BST