Course contentsShow
← Computer Science
Lesson 504 of 2,87212. Binary Search TreesFree lesson

BST Search: Iterative Implementation

Implement BST search iteratively using a loop instead of recursion for better space efficiency.

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:

  1. Compare the target with current's value
  2. Move current left or right based on the BST property
  3. Stop when you find the target or current becomes 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.