BST search

Search a value in O(log n) average.

BST search

Search in a BST follows binary-search logic. If the target is smaller than the root look in the left subtree, if larger look right. If we reach None the value is not present.

Each step halves the search space; a balanced BST gives O(log n). This is the same logic as binary search on a sorted array.

The BST advantage: insertion and deletion are equally fast; more flexible than an array.

Search cost

In a balanced BST search is O(log n) because each step halves the search space. This matches binary search on a sorted array.

But an unbalanced BST (e.g. inserting sorted data) becomes chain-like and search degrades to O(n). This is why balancing matters.

AVL or red-black trees provide automatic balance so search stays O(log n) always.

Exercise BST search

Write search(node, target). Smaller left, larger right, equal True, None False. Print True with root = Node(5); root.left = Node(3); print(search(root, 3)).

Show example solution

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def search(node, target):
    # Search in BST
    if node is None:
        return False
    if node.val == target:
        return True
    if target < node.val:
        return search(node.left, target)
    return search(node.right, target)
root = Node(5)
root.left = Node(3)
print(search(root, 3))

Test yourself

BST search: match the terms

Smaller

Left
Larger

Right
Equal

Found
None

Absent
Search cost in an unbalanced BST?
- O(1)
- O(n^2)
- O(log n)
- O(n)
Show answer

O(n) — O(n)

Found

if node.val == target: return ____

Show answer

if node.val == target: return True

Next lesson: Summary - BST

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies