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:

binarySearchTreeHasTarget(TreeNode.of([1]), 1)
# True

binarySearchTreeHasTarget(TreeNode.of([2, 1]), 1)
# True

binarySearchTreeHasTarget(TreeNode.of([2, 1]), 2)
# 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:

0. Problem

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

1. Recursion

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

2. Base case

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

hasTarget(None) = False

3. Code

def binarySearchTreeHasTarget(root, target):
    def hasTarget(node):
        # base case
        if node is None:
            return False
        # recursion
        if target == node.val: return True
        if target < node.val:  return hasTarget(node.left)
        else:                  return hasTarget(node.right)

    return hasTarget(root)

Time Complexity $O(\log n)$

Space Complexity $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

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!