Binary Trees and Binary Search Trees

The Guessing Game That's Secretly a Data Structure

Play this with a friend: think of a number between 1 and 100. Your friend guesses 50. You say "lower." They guess 25. You say "higher." They guess 37. You say "lower." Within about seven guesses, no matter what number you picked, they will find it — because every guess cuts the remaining possibilities roughly in half. You have almost certainly used this strategy before, and if you have studied binary search on a sorted array, you already know why it works: halving repeatedly shrinks 100 numbers to 1 very fast (100 to 50 to 25 to 13 to 6 to 3 to 1 in about seven steps).

Now do something different: instead of just playing the game, draw it. Put the first guess, 50, at the top of a page. Below it and to the left, draw the guess that happens when the answer is "lower" than 50. Below it and to the right, draw the guess for "higher." Keep going — every guess branches into at most two next guesses, one for each possible answer. Step back and look at the shape you have drawn. It is not a straight line and it is not a grid. It is a single starting point that splits into two, which each split into two again, narrowing down as you go deeper. That branching shape has a name in computer science: a binary tree. And when you use that exact shape to store real data — not just guesses in a game, but marks, names, PNR numbers, prices — arranged so that searching through it works exactly like this guessing game, you get one of the most useful structures in all of computer science: the Binary Search Tree, or BST.

This chapter builds the idea in order: what a tree is in general, what makes a tree "binary," what extra rule turns a binary tree into a search tree, how to insert and search in one by hand and in code, three standard ways to walk through a tree's contents, and two mistakes almost everyone makes the first time they meet this topic.

From Folders to Trees: General Vocabulary

Before narrowing to binary trees, it helps to see a tree that is not binary at all, because the vocabulary is easier to learn there first. Open File Explorer on a computer. The C: drive contains folders like Documents, Pictures, and Programs. Documents might contain School and Projects. School might contain Class8, which contains Notes.docx. Draw this as boxes connected by lines going downward, and you have a tree — and here a folder can have any number of sub-folders, not just two, so this is a general tree, not yet a binary one.

This picture gives us precise vocabulary that every tree, binary or not, uses:

• Node — a single box in the structure (a folder, or in the guessing game, one guess).
• Root — the node at the very top, with no parent above it (C: itself).
• Edge — the line connecting a node to one of the nodes directly below it.
• Parent / Child — if an edge connects node A above to node B below, A is B's parent and B is A's child. Documents is the parent of School.
• Siblings — nodes that share the same parent (School and Projects are siblings).
• Leaf — a node with no children at all (Notes.docx, or an empty folder).
• Subtree — any node together with everything below it, treated as a smaller tree of its own. The School folder and everything inside it is a subtree of Documents.
• Depth of a node — the number of edges on the path from the root down to that node. The root has depth 0.
• Height of a tree — the depth of its deepest leaf; the length of the longest root-to-leaf path.

These eight words describe every tree you will ever meet in computer science, whether it has two children per node or twenty.

What Makes a Tree "Binary"

A binary tree adds exactly one restriction to a general tree: every node has at most two children, and — unlike siblings in a folder tree, which have no order — the two children are distinguished by position: a left child and a right child. A node might have only a left child, only a right child, both, or neither (a leaf); it can never have three.

This restriction is exactly what the guessing game needs. Every guess has exactly two possible follow-ups: "the answer is smaller" (go left) or "the answer is larger" (go right). A structure with at most two positioned children per node is the natural shape for any process built on repeated two-way decisions — which is precisely why it shows up so often in search algorithms, decision logic, and expression parsing.

Here is a binary tree of seven nodes, built from a set of test marks out of 100. Look at its shape only for now — vocabulary labelled directly on the diagram:

The Extra Rule That Makes It a Search Tree

Shape alone does not make a tree useful for searching. The tree above happens to also be a Binary Search Tree, but that is because its values obey one extra rule, called the BST property:

For every node N in the tree — every single value in N's left subtree is smaller than N, and every single value in N's right subtree is larger than N.

Notice the phrase "every single value in the subtree," not just "N's immediate children." This distinction matters and is the source of the most common mistake in this topic, which the misconception section below deals with directly. For now, check the rule against the picture: at node 50, the entire left side (30, 20, 40) is smaller than 50, and the entire right side (70, 60, 80) is larger than 50. Zoom into node 30: its left side (20) is smaller than 30, its right side (40) is larger than 30. The rule holds at every node, not just the root.

Why does this one rule matter so much? Because it turns "search for a value" into the exact same one-question-at-a-time process as the guessing game: at any node, one comparison tells you which entire subtree could possibly contain your target — and you can throw away the other subtree completely, without looking at a single value inside it.

Worked Example: Building a BST One Insertion at a Time

Suppose a teacher enters seven students' marks into an empty BST in the order they were checked: 50, 30, 70, 20, 40, 60, 80. The insertion rule is always the same: start at the root and compare; go left if the new value is smaller, go right if it is larger; when you reach an empty spot, place the new node there.

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

The result is exactly the tree drawn above. Notice that each new value walked the same left/right path a search for that value would take — insertion in a BST is just "search for where this value would be, and put it there when you fall off the tree."

Searching a BST — and Why It Beats a Plain List

Search for 40 in the tree: start at root 50. Since 40 < 50, the entire right subtree (70, 60, 80) can be discarded without inspection — the BST property guarantees none of those values can be 40. Move to 30. Since 40 > 30, discard the entire left subtree of 30 (just the value 20) and move right, to 40. Compare: 40 = 40, found. That took three comparisons.

Compare this to storing the same seven marks in an unsorted list and scanning from the start: to find 40 you might get lucky, or in the worst case (searching for 80, the last one stored) you would need to check all seven, one by one. The BST's advantage is not magic — it comes directly from the fact that every comparison eliminates an entire subtree, not just one value.

This connects back to the guessing game and to log-base-2 reasoning, which is worth building carefully rather than stating as a formula. Think about how many nodes a binary tree of a given height can hold at most. At depth 0 there is room for 1 node (the root). At depth 1, each of those can have 2 children, so up to 2 nodes. At depth 2, up to 4. At depth 3, up to 8. Each level doubles the previous one, because every node can spawn two more. So a tree of height h — meaning h+1 levels, from depth 0 to depth h — can hold at most 1 + 2 + 4 + ... + 2^h nodes, which works out to 2^(h+1) − 1. Our seven-mark tree has height 2, and 2^3 − 1 = 7, exactly full. Turning this around: if you have n values and you keep the tree as short (balanced) as possible, the height only needs to grow to about log₂(n) — for the guessing game with 100 numbers, 2^7 = 128 ≥ 100, which is exactly why seven guesses are always enough. A balanced BST search costs roughly one comparison per level, so it costs about log₂(n) comparisons — dramatically fewer than n for large n. With a million records, log₂(1,000,000) is under 20, while scanning one by one could take a million steps.

Trace the search for 40 visually — the highlighted path shows exactly which comparisons happen and why the tree never looks at 20, 60, 70, or 80:

Traversals: Three Disciplined Ways to Visit Every Node

Sometimes you don't want to search for one value — you want to visit all of them, in some useful order. There are three standard recursive rules for walking a binary tree, and each is defined by where the node itself is visited relative to its two subtrees:

• Inorder — visit the entire left subtree, then the node, then the entire right subtree.
• Preorder — visit the node first, then the entire left subtree, then the entire right subtree.
• Postorder — visit the entire left subtree, then the entire right subtree, then the node last.

Applying all three to the marks tree (50, 30, 70, 20, 40, 60, 80 arranged as built above):

Inorder: 20, 30, 40, 50, 60, 70, 80.
Preorder: 50, 30, 20, 40, 70, 60, 80.
Postorder: 20, 40, 30, 60, 80, 70, 50.

Look closely at the inorder result: 20, 30, 40, 50, 60, 70, 80 — perfectly sorted, ascending. This is not a coincidence specific to this example; it is guaranteed for every BST, and it follows directly from the ordering rule. Inorder visits a node only after finishing its entire left subtree (everything smaller) and before starting its entire right subtree (everything larger) — so at every single node, everything printed before it is smaller and everything printed after it is larger, which is exactly the definition of a sorted sequence. This gives you a free sorting algorithm: build a BST from a list of numbers, then read it inorder.

Preorder and postorder are used differently. Preorder visits the node before its subtrees, which is useful when you need to reconstruct or copy the exact shape of a tree (you always place a node before its children, matching how the tree was originally built). Postorder visits a node only after both its subtrees are fully handled, which is why it is the natural order for deleting a tree node by node — you can safely delete both children before deleting their parent, since you will never need to reach through an already-deleted node.

Misconception 1: "Every Binary Tree Is a Binary Search Tree"

This is false, and it is the single most common error students make with this topic. Being "binary" is purely a statement about shape: at most two children per node. Being a "search tree" is a statement about the values obeying the ordering rule. A tree can be perfectly binary in shape and still break the BST rule completely — for example, root 50 with left child 70 and right child 20 is a valid binary tree (two children, correctly positioned as left and right) but not a BST, since 70 is not smaller than 50 and 20 is not larger than 50.

The deeper trap is subtler: checking only immediate parent-child pairs is not enough to confirm a tree is a valid BST. Consider this tree: root 50, left child 30, and 30's right child is 60. Check each edge individually: 30 < 50 — fine. 60 > 30 — fine. Every local parent-child comparison passes, and a careless check would call this a valid BST. But 60 sits inside 50's left subtree, and the BST rule requires everything in that entire subtree to be smaller than 50 — yet 60 > 50. The rule was violated two levels down, invisible to a check that only looks at direct parents and children. This is exactly why the earlier definition of the BST property was phrased "every value in N's left subtree," not "N's left child" — checking one level is not enough; the rule must hold against every ancestor, all the way up, not just the immediate parent.

Misconception 2: "A BST Search Is Always Fast"

The log₂(n) speed advantage assumed a balanced tree — one that stays short and wide. Nothing in the basic insertion rule guarantees that. Insert the same seven marks in already-sorted order instead — 20, 30, 40, 50, 60, 70, 80 — and trace it: 20 becomes the root; 30 is larger, so it becomes 20's right child; 40 is larger than 20 and larger than 30, so it becomes 30's right child; and so on. Every single value only ever goes right, because each new value is larger than everything already inserted. The result is a long diagonal chain, not a wide tree:

The fix computer scientists use is a self-balancing BST — a tree that automatically restructures itself (through operations called rotations) during insertion so its height never strays far from log₂(n), regardless of the order values arrive in. Grade-level BST code does not need to build one, but it is worth knowing they exist and are used constantly in practice: the AVL tree and the red-black tree are two standard designs, and the red-black tree specifically is what powers C++'s std::map and Java's TreeMap under the hood. The lesson to carry forward is not "learn AVL trees now" but "a BST's speed is a property of its shape, and shape depends on insertion order — never assume balance without checking."

Writing It in Code

Here is the BST built and used in Python, matching every step traced above exactly:

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return Node(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node  # duplicates are ignored

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, node, value):
        if node is None:
            return False
        if value == node.value:
            return True
        elif value < node.value:
            return self._search(node.left, value)
        else:
            return self._search(node.right, value)

    def inorder(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.value)
            self._inorder(node.right, result)


marks = [50, 30, 70, 20, 40, 60, 80]
tree = BST()
for m in marks:
    tree.insert(m)

print(tree.inorder())    # [20, 30, 40, 50, 60, 70, 80]
print(tree.search(40))   # True
print(tree.search(45))   # False

Trace search(45) by hand to see a "not found" case reach a dead end correctly: start at root 50 — 45 < 50, go left to 30 — 45 > 30, go right to 40 — 45 > 40, go right — but 40 has no right child, so the recursion reaches None and returns False. The function correctly reports that 45 is absent after only three comparisons, without ever scanning the whole tree.

Where This Actually Gets Used

Large-scale record lookup relies on this same idea, just extended. A railway reservation system holding tens of millions of PNR records cannot scan them one by one every time a passenger checks status — it needs something with the "throw away half the remaining data per comparison" property a BST provides. Real database engines usually go one step further and use a B-tree (a generalization that allows more than two children per node, tuned to how disk storage reads data in blocks), but the underlying principle — an ordered branching structure that turns a linear scan into a logarithmic one — is the same idea this chapter just built by hand with marks out of 100.

Practice

1. Insert 45, 25, 65, 10, 35, 55, 75 into an empty BST in that order. Draw the resulting tree, labelling which nodes are leaves.
2. Without recomputing the tree, predict the inorder traversal of the tree from question 1. Then verify it by walking left-node-right yourself.
3. Trace a search for 35 in that same tree. List each comparison made and state how many there were.
4. A binary tree has root 8, left child 3, and 3 has a right child 10. Is this tree a valid BST? Justify your answer using the subtree rule, not just the immediate parent-child comparisons.
5. A BST holds exactly 15 nodes and is perfectly balanced (every level as full as possible). What is its height? (Hint: use the 2^(h+1) − 1 relationship from the search-cost section.)
6. Explain, in your own words, why inserting data that is already sorted produces the worst possible BST shape, and name one real data structure used to prevent this problem.

Summary

• A tree is nodes connected by edges from a root downward; key vocabulary is parent, child, sibling, leaf, subtree, depth, and height.
• A binary tree restricts every node to at most two positioned children: left and right.
• A Binary Search Tree adds an ordering rule: at every node, its entire left subtree is smaller and its entire right subtree is larger — checked against every ancestor, not just the immediate parent.
• Insertion walks left/right by comparison until it finds an empty spot; search follows the identical path and either finds the value or falls off the tree.
• A balanced BST search costs about log₂(n) comparisons because each comparison eliminates an entire subtree — dramatically fewer than scanning n items one by one.
• Inorder traversal (left, node, right) always outputs a BST's values in sorted order; preorder (node, left, right) and postorder (left, right, node) serve copying and deletion respectively.
• Not every binary tree is a BST, and a BST built from already-sorted input can degrade into a worst-case chain with height n − 1, losing all speed advantage — which is why real systems use self-balancing variants like AVL or red-black trees.