Search follows the BST property directly:
def search(root, target):
if root == null:
return null
if target == root.val:
return root
if target < root.val:
return search(root.left, target)
else:
return search(root.right, target)
Iterative version:
def search(root, target):
while root and root.val != target:
if target < root.val:
root = root.left
else:
root = root.right
return root
Time: where is tree height. Space: for iterative, for recursive.
In a balanced tree, . In the worst case (skewed), .