Binary Search Tree Insert and Search: One Comparison per Level

A binary search tree keeps one promise: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. Search and insert both follow from that promise, and they turn out to be the same walk. Interviewers use the pair as the first real tree question, because the code is short and the follow-ups are not: why the cost is the height and not log n, what sorted input does, and how to find the closest value when the exact one is missing.

The problem it solves

A sorted array answers "is 45 here?" in O(log n), but each insert shifts everything after the insertion point, O(n). A hash set is constant time on average, but has no order: it cannot give the largest value below 45, or list keys in order.

A BST sits in between. It keeps keys ordered like the sorted array, but a new key is linked in rather than shifted into place. Search, insert, minimum, maximum, floor, ceiling and in-order listing all come from one structure.

The intuition

At each node, one comparison decides everything. If the target is smaller, it can only be in the left subtree, so the whole right subtree is discarded; if larger, the left side goes. It is binary search on a linked structure: each step throws away one side.

Search repeats that step until it finds the value or falls off the tree into an empty slot. Falling off means the value is absent.

Insert is the same walk. It goes left or right exactly as a search for the new value would, and at the empty slot where that search would have failed, it hangs the new node. That is why insert and search always agree: a value is found later by the path that placed it.

The cost of both is one step per level, so it is O(h), the height of the tree. The height is where the promise can go wrong. Keys arriving in random order give a bushy tree whose height grows like log n. Keys arriving sorted all go right, one after another, and the tree becomes a linked list of height n. The BST property still holds; it is just useless. Balanced trees such as AVL and red-black trees add rotations to keep the height logarithmic; Java's TreeMap is a red-black tree, and C++'s std::map is usually one.

Duplicates need one rule: reject them, count them, or always send them the same way. The code below sends them right.

Watch it run

The animation runs the lesson's script. The tree starts as a single root, 50, and every insert walks down from there. Insert 30: 30 is less than 50, so go left; that slot is empty, so 30 lands there. Insert 70: greater, so right, and the slot is free. Insert 20: left at 50, and the whole right side is out of the question from here on; left again at 30, and 20 lands after two comparisons. Insert 40: left at 50, right at 30, and it lands. Now search(40), one comparison per level, the losing side discarded outright. At 30, go right; two of the five nodes are already gone, and 40 is found. The cost is O(h), the height, not O(n). Then search(45) walks the identical path, left at 50, right at 30, right at 40, and that slot is empty: False. The last frame points out that this empty slot is exactly where insert(45) would put it; insert and search walk the same path.

The code

An iterative insert, so a tall tree cannot hit Python's recursion limit, and a search that returns the path it walked. The two searches from the animation take the same path; inserting 45 then lands in the slot where the second one failed:

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

def insert(root, val):
    """Walk the search path; hang the new node on the first empty slot."""
    if root is None:
        return Node(val)
    node = root
    while True:
        if val < node.val:
            if node.left is None:
                node.left = Node(val)
                return root
            node = node.left
        else:                              # duplicates go right: one fixed rule
            if node.right is None:
                node.right = Node(val)
                return root
            node = node.right

def search_path(root, val):
    path, node = [], root
    while node:
        path.append(node.val)
        if val == node.val:
            return True, path
        node = node.left if val < node.val else node.right   # one side discarded
    return False, path

root = None
for v in [50, 30, 70, 20, 40]:
    root = insert(root, v)
print(search_path(root, 40))               # (True, [50, 30, 40])
print(search_path(root, 45))               # (False, [50, 30, 40])
root = insert(root, 45)                    # lands exactly where the search failed
print(root.left.right.right.val)           # 45

Why the height is the bill. An in-order walk lists the keys sorted. Then the same 1,000 keys go in twice, once sorted and once shuffled with a fixed seed, and the heights and search paths are compared:

import random

def inorder(node, out):
    if node:
        inorder(node.left, out); out.append(node.val); inorder(node.right, out)
    return out

def height(root):
    best, stack = 0, [(root, 1)] if root else []
    while stack:
        node, depth = stack.pop()
        best = max(best, depth)
        stack += [(child, depth + 1) for child in (node.left, node.right) if child]
    return best

print(inorder(root, []))                   # [20, 30, 40, 45, 50, 70]

random.seed(25)
keys = list(range(1, 1_001))
chain = None
for k in keys:                             # sorted input: every key goes right
    chain = insert(chain, k)
shuffled = keys[:]
random.shuffle(shuffled)
bushy = None
for k in shuffled:
    bushy = insert(bushy, k)
print(height(chain), height(bushy))                                  # 1000 24
print(len(search_path(chain, 1_000)[1]), len(search_path(bushy, 1_000)[1]))   # 1000 8

The follow-up that comes next: the largest key at or below x, and the smallest at or above it, in one walk. Every time the walk goes right, the current node is a candidate floor; every time it goes left, a candidate ceiling:

def floor_ceiling(root, x):
    floor = ceiling = None
    node = root
    while node:
        if node.val == x:
            return x, x
        if node.val < x:
            floor, node = node.val, node.right    # a floor; look for a bigger one
        else:
            ceiling, node = node.val, node.left   # a ceiling; look for a smaller one
    return floor, ceiling

print(floor_ceiling(root, 42), floor_ceiling(root, 10), floor_ceiling(root, 99))
# (40, 45) (None, 20) (70, None)

Checked on 1,500 seeded random trees with duplicates: the in-order walk must equal sorted, every search must agree with a membership test, floor and ceiling must equal a brute-force scan, and no search path may be longer than the height:

ok = True
for _ in range(1_500):
    values = [random.randint(0, 40) for _ in range(random.randint(0, 25))]
    tree = None
    for v in values:
        tree = insert(tree, v)
    ok &= inorder(tree, []) == sorted(values)
    for x in range(-2, 43):
        ok &= search_path(tree, x)[0] == (x in values)
        lo = max((v for v in values if v <= x), default=None)
        hi = min((v for v in values if v >= x), default=None)
        ok &= floor_ceiling(tree, x) == (lo, hi)
    ok &= len(search_path(tree, 99)[1]) <= height(tree)
print(ok)                                  # True

The complexity

• Search and insert: O(h). On random input h grows like log n; on sorted input h = n.
• Balanced trees: O(log n) guaranteed, paid for with rotations on insert and delete.
• Space: O(n) nodes. The iterative versions need O(1) extra; recursive ones use O(h) stack.
• In-order listing: O(n), and it comes out sorted, which binary tree traversals covers in detail. The Big-O cheat sheet lists BST costs next to the other structures.

Where it goes wrong

• Calling it O(log n) without the qualifier. Only for a balanced or random tree.
• Recursive insert on a tall tree. A 1,000-deep chain hits Python's default recursion limit; walk it with a loop.
• No duplicate rule. Sending equal keys left sometimes and right other times makes search miss them.
• Checking only the parent. Validity is about whole subtrees, not just each node's children, as validate BST shows.
• Losing the root. Inserting into an empty tree must return it.

When it shows up in interviews

"Insert into a BST" and "search a BST" are warm-ups for questions built on the same walk: closest value, floor and ceiling, the lowest common ancestor in a BST, and the k-th smallest via in-order. Sorted input turning the tree into a chain is the classic follow-up, and the expected answer is a balanced tree.

How to say it in an interview

"At each node I compare once: smaller goes left, larger goes right, and the other subtree is discarded. Search stops on a match or an empty slot. Insert walks the same path and puts the new node in the empty slot where the search would have failed, so the two always agree. Both cost O(h). That is O(log n) for a balanced or random tree, but sorted input builds a chain with h = n, which is why production trees rebalance. I write it iteratively, so height never hits a recursion limit."