BST Search: Iterative Implementation
What you'll learn: How to search a Binary Search Tree using a loop instead of recursion to save memory.
Why Use Iteration?
In the previous lesson, you learned how to search a BST recursively. While recursion is elegant, it uses the call stack to remember where you've been—which consumes memory proportional to the tree's height. An iterative approach using a simple while loop achieves the same result with constant space (O(1)), making it more efficient in practice.
The Core Idea
Instead of calling the function again on child nodes, maintain a current pointer that starts at the root. Use a loop to repeatedly:
- Compare the target with
current's value - Move
currentleft or right based on the BST property - Stop when you find the target or
currentbecomes null
Think of it like descending stairs: instead of remembering every step you took (recursion), you just keep track of which stair you're standing on right now.
Implementation
def search_iterative(root, target):
current = root
while current is not None:
if target == current.value:
return current # Found it!
elif target < current.value:
current = current.left # Go left
else:
current = current.right # Go right
return None # Not found
The logic is identical to recursion: compare, decide, move. But instead of function calls building up on the stack, you're just reassigning a single variable.
Time complexity: Still O(h) where h is height—same as recursive.
Space complexity: O(1)—just one pointer variable.
Key Takeaway: Iterative BST search replaces recursive calls with a loop and a moving pointer, achieving the same result with better space efficiency.