Tree Traversal Target: 10s
BST search: go left if target < node, right if target > node. O(h) time. Must be instant.
def searchBST(root, val):
while root:
if val == root.val: return root
elif val < root.val: root = root.left
else: root = root.right
return None
# Recursive:
def searchBST_rec(root, val):
if not root or root.val == val: return root
if val < root.val: return searchBST_rec(root.left, val)
return searchBST_rec(root.right, val)Type it from memory. Go.