Easy Recursive Descent Trees
In plain English: Look up whether a value exists in a binary search tree.
BST property halves the search space at each step — go left if smaller, right if larger, like binary search on a tree.
Prompt
Search for a value in a BST. Return the node or None.
Try to write it from scratch before scrolling down.
Solution
def bst_search(root, val):
if root is None or root.val == val:
return root # base: found or exhausted
if val < root.val:
return bst_search(root.left, val) # BST: smaller goes left
return bst_search(root.right, val)
# Iterative:
def bst_search_iter(root, val):
while root and root.val != val:
root = root.left if val < root.val else root.right # halve search space
return root