Search in a BST

Table of Contents +

Say you have a phone book with thousands of names. You need to find “Riya”. Do you read every page from the start? No. You open somewhere in the middle. You check if Riya comes before or after. Then you jump to the right half. You keep cutting the search in half. Searching a Binary Search Tree works the same way. It is just as fast.

A Binary Search Tree is a tree where every node follows one rule. Smaller values sit on the left. Larger values sit on the right. Because of this rule, you never have to look at the whole tree. At each node you can throw away one full side.

🎯 What Are We Trying to Do?

The pain is simple. You have a tree full of values. Someone asks “is 40 in here?” If you check every single node, that is slow. A search tool that touches every item is no better than a plain list.

Searching a BST fixes that. You use the left-small, right-large rule to skip half the tree at each step. So you reach your answer in very few jumps.

Here is the idea in plain words:

Start at the root, the topmost node of the tree.
If the target equals the current node value, you found it. Stop.
If the target is smaller than the current node, go to the left child.
If the target is larger, go to the right child.
Repeat this on the new node.
If you ever reach an empty spot (no child there), the value is not in the tree.

🌳 The Sample Tree

Let us use one tree for all our examples. We will search it twice. Once for a value that exists. Once for a value that does not.

The root is 50. Smaller values like 30, 20, and 40 went to the left side. Larger values like 70, 60, and 80 went to the right side. Notice how the rule holds at every node, not just the root.

🔍 Walking Through a Search

Let us search for 40. Follow along and see how we cut the tree down.

Start at the root, 50. Is 40 equal to 50? No. Is 40 smaller than 50? Yes. So go left to 30.
Now at 30. Is 40 equal to 30? No. Is 40 smaller than 30? No, it is larger. So go right to 40.
Now at 40. Is 40 equal to 40? Yes. Found it.

See that? We found 40 in three steps. We never even looked at 70, 60, 80, or 20. That whole right side got skipped.

Now let us search for 45, a value that is not in the tree.

Start at 50. 45 is smaller. Go left to 30.
At 30. 45 is larger. Go right to 40.
At 40. 45 is larger. Go right. But 40 has no right child. We reached an empty spot. So 45 is not here.

When you reach an empty spot, that is your signal the value does not exist.

📝 Steps to Search a BST

Before we write code, let us put the plan in clear order. We will do this both the recursive way and the iterative way.

Begin at the root node.
If the current node is empty (null), the value is not in the tree. Return “not found”.
Compare the target with the current node’s value.
If they are equal, return “found”.
If the target is smaller, move to the left child and repeat from step 2.
If the target is larger, move to the right child and repeat from step 2.

That is the whole algorithm. Now let us turn it into real code.

💻 Recursive Search

The recursive version reads almost exactly like the steps above. The function calls itself on the left or right child until it finds the value or reaches an empty spot. This way of calling itself is called recursion.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

# A node holds a value and links to two children
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Insert a value so the tree stays a BST
def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

# Search the tree the recursive way
def search(root, target):
    if root is None:               # empty spot, not found
        return False
    if target == root.value:       # found it
        return True
    if target < root.value:
        return search(root.left, target)   # smaller, go left
    return search(root.right, target)      # larger, go right

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

print("Searching 40:", "Found" if search(root, 40) else "Not Found")
print("Searching 45:", "Found" if search(root, 45) else "Not Found")

The output of the above code will be:

Searching 40: Found
Searching 45: Not Found

Note

Average time is O(log n). Each step throws away one half of the remaining tree, so the work shrinks fast. Space is O(h) where h is the height of the tree, because the recursion stacks up one call per level.

🔁 Iterative Search

The recursive version is clean. But every call uses a little memory on the call stack. The iterative version does the same walk with a simple loop. There are no extra calls, so it uses constant extra space.

The logic is the same. We just move a pointer down the tree inside a while loop instead of calling the function again.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

# Search using a loop instead of recursion
def search(root, target):
    current = root
    while current is not None:
        if target == current.value:    # found it
            return True
        if target < current.value:
            current = current.left      # smaller, go left
        else:
            current = current.right     # larger, go right
    return False                        # empty spot

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

print("Searching 40:", "Found" if search(root, 40) else "Not Found")
print("Searching 45:", "Found" if search(root, 45) else "Not Found")

The output of the above code will be:

Searching 40: Found
Searching 45: Not Found

Tip

The iterative version uses O(1) extra space because it only keeps one pointer. The recursive version uses O(h) space for the call stack. Both do the same number of comparisons, so the time is the same.

⏱️ Time and Space Complexity

The speed of the search depends on the shape of the tree. A balanced tree is short and wide. So you reach any value in few steps. An unbalanced tree leans to one side like a long chain. So a search can end up checking almost every node.

Case	Time	Space (Recursive)	Space (Iterative)
Average (balanced tree)	O(log n)	O(log n)	O(1)
Worst (unbalanced, chain-like tree)	O(n)	O(n)	O(1)

Caution

If you insert values in sorted order like 10, 20, 30, 40, the tree becomes one long line to the right. Now a search walks every node, which is O(n). This is why balanced trees matter. You will see how to keep trees balanced in later topics.

🧩 What You’ve Learned

✅ A BST search starts at the root and uses the left-small, right-large rule to skip half the tree at each step.
✅ You compare the target with the current node, then go left if smaller, right if larger, and stop when they match.
✅ When you reach an empty spot, the value is not in the tree.
✅ You can write the search with recursion (calls itself) or with a loop (iterative), and both give the same answer.
✅ Average search time is O(log n), but an unbalanced tree drops it to O(n) in the worst case.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Introduction to Binary Search Trees
Insert in a BST

Previous Introduction to Binary Search Trees Next Insert in a BST

Share & Connect

Share on LinkedIn