The recursive solution is clean:
def searchBST(root, val):
if root == null or root.val == val:
return root
if val < root.val:
return searchBST(root.left, val)
return searchBST(root.right, val)
The iterative solution uses constant space:
def searchBST(root, val):
while root and root.val != val:
root = root.left if val < root.val else root.right
return root
Time: . Space: iterative, recursive.
This problem is foundational—make sure you can write it quickly without thinking.