Binary search trees: why the order you insert numbers changes how fast you can find them

Suppose you keep a list of a million numbers and want to know whether 73,914 is in it. In an unsorted list you may have to check every number. If the list is sorted, binary search needs about 20 guesses. But a sorted list has a catch: adding a new number in the middle means shifting everything after it along by one place. Is there a way to keep data in order and add to it cheaply? There is, and it is called a binary search tree.

One rule, made of boxes

A node is a small box holding a value and two links, left and right, each pointing to another node or to nothing. A tree is nodes linked this way, starting from one node at the top called the root. A node with no children is a leaf.

The "binary search" part is a single rule, applied at every node: everything in the left branch is smaller than this node, and everything in the right branch is bigger. That is all. To find a value, start at the root and compare. Smaller? Go left. Bigger? Go right. Equal? Found it. Reach a link that points to nothing? It isn't there.

Build one and watch it search

Type a number and press Insert, or use the presets. Then type a number in the Find box: the nodes visited light up, and the count is the number of comparisons made.

Try "Mixed order" and find 80: three comparisons. Now press "Sorted order" and find 80 again: seven. Same numbers, same rule, very different shape. The shape depends on the order you inserted them in.

Why order changes the shape

The first number inserted becomes the root and never moves. Every later number walks down from the root using the same smaller-left, bigger-right rule and attaches itself at the first empty link it meets. If you insert 20, then 30, then 40, each one is bigger than everything before it, so each goes right, then right again. The tree becomes a chain, which is really a linked list in disguise, and searching it means checking one node at a time.

The height of a tree is the number of levels from the root down to the lowest leaf. A search never makes more comparisons than the height, so height is the number to watch.

The code

Each node is a tiny object, and the functions call themselves on a smaller branch (if recursion is new, see the recursion article):

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

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node

def contains(node, value, steps=0):
    if node is None:
        return False, steps
    steps += 1
    if value == node.value:
        return True, steps
    if value < node.value:
        return contains(node.left, value, steps)
    return contains(node.right, value, steps)

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

Building two trees from the same seven numbers and searching for 80 in each prints this (we ran it with Python 3):

mixed order  height: 3 find 80: (True, 3)
sorted order height: 7 find 80: (True, 7)

Duplicates are ignored here, because neither the < nor the > branch matches an equal value.

What this means at scale

A tree that stays reasonably balanced, with both sides about equally full, has a height of roughly log₂ of the number of nodes. A million nodes fit in about 20 levels, so a search takes around 20 comparisons, the same as binary search. A tree that has collapsed into a chain over a million nodes needs up to a million comparisons.

That gap is why real systems don't use a plain tree on data that might arrive already sorted (timestamps and auto-incrementing ids often do). They use self-balancing trees, such as red-black trees or the B-trees many databases use for indexes. These rearrange nodes as you insert so the height stays near the minimum. You don't need to learn how they do it yet, only why they must: a tree is fast only while it stays short.

So the takeaway for your own code: a structure that keeps data in order can make both adding and searching quick, but only if its shape stays healthy. When a tool promises "fast lookups", it is worth asking what keeps it balanced.