Recursion

Search a BST

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

Example:

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

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

First Few Test Cases:

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:

0. Problem

1. Recursion

2. Base case

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

3. Code

Time Complexity $O(\log n)$

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

You can easily make this iterative:

Time Complexity $O(\log n)$

Space Complexity $O(1)$

Mark as Completed:

Submits:

binarySearchTreeHasTarget

Imports:

TreeNode

Test your code to get an output here!

binarySearchTreeHasTarget(

)

Test your code to get an output here!