Binary Search Trees

Open the roll-number register your class teacher keeps — the one where every student's marks are written in order of roll number, 1 to 45. Two operations happen to that register all the time. First, finding a student: flip to roughly the middle, see whether the roll number you want is higher or lower, and jump left or right — you can find any of 45 students in about six flips. Second, admitting a new student mid-year with a roll number that falls between two existing ones: you cannot just write it at the end. Every entry after the insertion point has to be copied one line down to make space. The register that made searching fast is exactly the register that makes inserting slow. Binary search trees exist to fix this — they give you the fast search of a sorted list without paying the price of a shift every time something new arrives.

Why a Sorted List Isn't Enough

Picture a sorted array of seven numbers, stored at indices 0 through 6:

index:  0   1   2   3   4   5   6
value: 20  30  40  50  60  70  80

Binary search finds any of these values in at most 3 comparisons (log₂7 rounded up), which is the whole appeal of keeping data sorted. Now insert 35. It belongs between 30 and 40, at index 2. But index 2 is occupied by 40, and every index after it is occupied too — 50, 60, 70, 80 are all sitting exactly where they were before. To open up a slot, the array has to physically shift things: 80 slides into where 70 was, 70 slides into where 60 was, 60 slides into where 50 was, 50 slides into where 40 was, and 40 finally slides into where 35 is about to go. Only after all five of those moves can 35 actually be written into index 2. Five shifts, for one insertion, in a 7-element array. If the array held 10,000 sorted roll numbers and you inserted near the front, you could be looking at close to 10,000 shifts. Searching stayed fast; inserting became the bottleneck.

An unsorted list dodges the shifting problem — you can append a new value at the end in one step — but then you lose binary search entirely, because binary search only works when the data is ordered. You are stuck choosing between fast search with slow insertion, or fast insertion with slow (linear, one-by-one) search. A binary search tree is the data structure that refuses to make that trade-off.

From List to Tree: A New Way to Stay Ordered

The core idea is to stop storing values in one continuous block of memory and instead store each value in its own small unit called a node. Each node holds a value and two arrows — a left pointer and a right pointer — each of which either points at another node or points at nothing. One node is designated the root, the starting point for every search. A node with no children is called a leaf. Because it is stored this way, adding a new node never requires moving any existing node — it just requires attaching a new arrow. That single design choice is what will let insertion avoid the shifting problem entirely.

Of course, scattering values across separate nodes only helps if there is still a rule connecting them — otherwise you could never search efficiently, since the values wouldn't be in any predictable order. That rule is the binary search tree property.

The Binary Search Tree Rule

A binary search tree (BST) is a tree of nodes, each with at most two children, that obeys one ordering rule at every single node:

• Every value in the node's left subtree (not just the immediate left child — every node anywhere below it on the left) is less than the node's own value.
• Every value in the node's right subtree (all of it, at every depth) is greater than the node's own value.
• This same rule applies again, recursively, at every node in the tree — the left child's left subtree must be smaller than the left child, and so on, all the way down.

That phrase "the entire subtree, not just the immediate child" is the part students most often skip past, and it is the part that actually makes the structure searchable — we'll return to why in the misconceptions section below.

Building a BST, One Insertion at a Time

Take the same seven numbers as the array example — 50, 30, 70, 20, 40, 60, 80 — but insert them one at a time into an empty tree, in that order, using this rule: to place a new value, start at the root and repeatedly go left if the new value is smaller than the current node, or right if it is larger, until you fall off the tree into empty space — that empty space is where the new node attaches.

• Insert 50: the tree is empty, so 50 becomes the root.
• Insert 30: compare to root 50 — 30 < 50, go left. Left of 50 is empty, so 30 attaches there.
• Insert 70: compare to 50 — 70 > 50, go right. Right of 50 is empty, so 70 attaches there.
• Insert 20: compare to 50 — smaller, go left to 30. Compare to 30 — smaller, go left. Empty, so 20 attaches as 30's left child.
• Insert 40: compare to 50 — smaller, go left to 30. Compare to 30 — larger, go right. Empty, so 40 attaches as 30's right child.
• Insert 60: compare to 50 — larger, go right to 70. Compare to 70 — smaller, go left. Empty, so 60 attaches as 70's left child.
• Insert 80: compare to 50 — larger, go right to 70. Compare to 70 — larger, go right. Empty, so 80 attaches as 70's right child.

The resulting tree:

Check the rule at the root: everything under 30 (that's 20, 30, 40) is less than 50, and everything under 70 (60, 70, 80) is greater than 50. Check it again at node 30: 20 is less, 40 is greater. The rule holds at every node, not just the root — that's what "binary search tree" actually guarantees.

Searching a BST

Searching mirrors the insertion path exactly. To search for 60: start at the root, 50. Since 60 > 50, move right to 70. Since 60 < 70, move left to 60. That matches the target — found, in 3 comparisons. Notice what just happened: at each node, one comparison eliminated an entire subtree from consideration. Comparing to 50 and going right didn't just skip 50 — it discarded 30, 20, and 40 in a single step, because the BST rule guarantees none of them could possibly be 60.

Here is the search written as Python, using a simple node class:

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

def search(root, target):
    current = root
    comparisons = 0
    while current is not None:
        comparisons += 1
        if target == current.value:
            return True, comparisons
        elif target < current.value:
            current = current.left
        else:
            current = current.right
    return False, comparisons

Trace search(root, 60) on the tree above: current starts at node 50, comparisons becomes 1, 60 > 50 so current moves to node 70. comparisons becomes 2, 60 < 70 so current moves to node 60. comparisons becomes 3, 60 == 60, so the function returns (True, 3). If instead you searched for 45 — a value not in the tree — the path would be 50 (go left, 45<50), 30 (go right, 45>30), 40 (go right, 45>40), then current becomes None and the loop ends, returning (False, 3). Even confirming that a value is absent only costs as many comparisons as the tree is deep — you never have to check all seven nodes.

Inserting into a BST

def insert(root, value):
    if root is None:
        return Node(value)
    current = root
    while True:
        if value < current.value:
            if current.left is None:
                current.left = Node(value)
                return root
            current = current.left
        elif value > current.value:
            if current.right is None:
                current.right = Node(value)
                return root
            current = current.right
        else:
            return root  # value already present; BSTs here don't store duplicates

Now insert 35 into the same tree that holds 20, 30, 40, 50, 60, 70, 80. Start at 50: 35 < 50, go left to 30. At 30: 35 > 30, go right to 40. At 40: 35 < 40, and 40's left pointer is empty, so 35 attaches there as 40's left child.

That took 3 comparisons and one new node — nothing already in the tree was touched, moved, or copied. Compare that to the sorted-array version of the same insertion, which needed five shifts (80, 70, 60, 50, and 40 each sliding one slot over) before 35 could even be written down. The tree traded "shift a chunk of memory" for "attach one pointer," and that trade is the entire reason binary search trees exist.

The Hidden Order: In-Order Traversal

A BST doesn't just support fast search and insertion — it can also hand back every value it holds in sorted order, without you sorting anything, using a walk called an in-order traversal: recursively visit the left subtree, then record the current node's value, then recursively visit the right subtree.

def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.value)
    inorder(node.right, result)

Run this on the seven-node tree (before inserting 35) and it produces [20, 30, 40, 50, 60, 70, 80] — sorted, automatically. This isn't a coincidence: at every node, the rule guarantees everything smaller is in the left subtree and everything larger is in the right subtree, so visiting left-self-right at every level necessarily produces values in increasing order. This is genuinely useful — it means a BST can serve as a sorted list whenever you need one, while still supporting cheap insertion the rest of the time.

Two Misconceptions to Retire

Misconception 1: "Any binary tree with two children per node is a binary search tree." It is not. A binary tree is just a shape — each node has at most two children, full stop, no ordering requirement. Consider a tree with root 50, left child 30, and then give 30 a right child of 60. Locally, at node 30, this might look fine — 60 is just "the right child of 30." But 60 sits inside 50's left subtree, and the BST rule requires everything in 50's left subtree to be less than 50. It is not (60 > 50), so this tree fails the BST property, even though every single node still has at most two children. The rule is about the entire subtree beneath a node, applied recursively at every level — not just about comparing a node to its immediate parent.

Misconception 2: "Searching a BST is always O(log n), like binary search on an array." This is only true when the tree is reasonably balanced — roughly the same number of nodes on the left and right of every node. Nothing in the BST rule forces that balance. The next section shows exactly how badly it can fail.

When Trees Go Wrong: The Skewed Tree

Insert 10, 20, 30, 40, 50 into an empty BST, in that already-sorted order. Insert 10: it becomes the root. Insert 20: 20 > 10, and 10 has no right child, so 20 attaches as 10's right child. Insert 30: 30 > 10, go right to 20; 30 > 20, and 20 has no right child, so 30 attaches there. The same thing happens for 40 and 50 — each new value is larger than everything already in the tree, so it always goes right, and only right.

Every node has only a right child — no node ever branches left. The BST rule is still perfectly satisfied at every node (there is no violation here at all), but the tree has degenerated into a straight chain, indistinguishable in shape from a plain linked list. Its height — the number of edges from the root down to the deepest node — is 4 for these 5 nodes: one less than the node count, because a chain of n nodes has exactly n−1 edges. Searching for 50 now means checking 10, then 20, then 30, then 40, then 50 — 5 comparisons to find the very last value, exactly the linear-scan behaviour a BST is supposed to avoid. This is why the honest complexity statement for BST search and insertion is O(h), where h is the tree's height — and h can be as small as about log₂n for a balanced tree, or as large as n−1 for a fully skewed one. Real-world BST implementations (like AVL trees or red-black trees, which you'll meet in later years) add extra rules specifically to stop this skew from happening; a plain BST offers no such guarantee on its own.

BST vs Sorted Array vs Unsorted List

• Unsorted list: insert is O(1) — just append; search is O(n) — must check every element, since there's no order to exploit.
• Sorted array: search is O(log n) via binary search; insert is O(n) in the worst case, because of the shifting shown earlier.
• Balanced BST: both search and insert are O(h) ≈ O(log n) — no shifting, because insertion just attaches a pointer, and no linear scanning, because each comparison still discards an entire subtree.
• Skewed BST: both degrade to O(n), because the height h has grown to roughly n instead of staying near log n.

A balanced BST is the only one of these four that offers fast search and fast insertion at the same time — which is precisely the combination a sorted array could not deliver.

Practice: Test Your Understanding

1. Insert 45, 15, 79, 90, 10, 55 into an empty BST, in that order. Draw the resulting tree and state its height (edges from root to deepest node).
2. Is [50, 30, 70, 20, 40, 65, 80] a possible in-order traversal output of some BST? Justify your answer using the in-order traversal rule.
3. A BST contains only 10, 20, 30, 40, 50, inserted in that exact order. What shape does it take, and how many comparisons does searching for 50 require?
4. Explain, in your own words, why a BST built from already-sorted input behaves like a plain linked list when you search it.
5. True or false, and correct it if false: "Any tree where every node has at most two children is automatically a binary search tree."

Answers. (1) 45 is the root; 15 attaches left of 45, with 10 attaching left of 15; 79 attaches right of 45, with 55 attaching left of 79 and 90 attaching right of 79. The deepest nodes (10, 55, 90) are 2 edges from the root, so the height is 2. (2) No — in-order traversal of any BST always outputs values in strictly increasing order, and this list is not sorted (70 appears before 20), so no BST could have produced it via in-order traversal. (3) Every insertion is larger than everything already present, so each new node becomes the right child of the previous one, forming a straight chain (height 4 for 5 nodes); searching for 50 must visit 10, 20, 30, 40, 50 in turn — 5 comparisons. (4) Because every insertion goes the same direction (always right, or always left), no node ever gets a second child, so the tree never branches — search has to move one node at a time just like following a linked list's next-pointer, giving O(n) instead of O(log n). (5) False — a binary tree only restricts how many children a node may have; the BST property additionally requires that a node's entire left subtree be smaller than it and its entire right subtree be larger, at every level, which a merely-binary tree is not required to satisfy.

Summary

A sorted array gives fast search but forces expensive shifting on every insertion, because its values live in one contiguous, ordered block. A binary search tree keeps values in independent nodes connected by left and right pointers, governed by one rule applied at every node: the entire left subtree is smaller, the entire right subtree is larger. That rule lets search discard half the remaining tree at each comparison, exactly like array binary search, while letting insertion attach a single new node without moving anything that already exists — five array shifts became three tree comparisons and one attachment for the same value in the same data set. An in-order traversal (left, self, right) always recovers the values in sorted order, for free. But the BST rule alone guarantees nothing about shape: insert already-sorted data and the tree degenerates into a one-directional chain with height close to n, and search cost degrades from O(log n) to O(n) even though every node still obeys the rule perfectly. The real complexity of BST operations is O(h), the tree's height — small and logarithmic when the tree is balanced, and as large as n−1 when it isn't, which is exactly why balanced variants of the BST exist.

Think About It

Think about this: How would you explain binary search trees to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.