Trees & Binary Search Trees

What is a tree?#

Every data structure so far in this course has been linear — arrays, linked lists, stacks, and queues all arrange data in a single sequence, one item after another. A tree is the first hierarchical structure we've covered: data organized in parent-child relationships, branching outward from a single starting point.

Analogy: a family tree, or the folder structure on your computer. A folder can contain files and other folders, which can contain more files and folders, branching downward indefinitely. There's exactly one "top" (your root drive), and everything else sits somewhere underneath it, reachable by following a single path down from the top.

Tree terminology#

Before writing any code, it's worth locking in the vocabulary — every tree-related explanation you'll ever read (including the rest of this page) leans on these terms constantly:

• Root — the single node at the very top of the tree, with no parent.
• Node — any single element in the tree, holding a value and references to its children.
• Edge — the connection between a parent node and a child node.
• Leaf — a node with no children — the "ends" of the branches.
• Parent / Child — a node directly above/below another, connected by one edge.
• Depth (of a node) — the number of edges from the root down to that node. The root has depth 0.
• Height (of a tree, or of a node) — the number of edges on the longest downward path from that node to a leaf. The height of the whole tree is the height of its root.

        A          <- root, depth 0
       / \
      B   C        <- depth 1
     / \
    D   E          <- depth 2, both leaves (D and E have no children)

In this small tree: A is the root, D and E are leaves, B is the parent of D and E, the depth of E is 2, and the height of the whole tree is 2 (the longest root-to-leaf path is A -> B -> D, two edges).

Binary trees vs binary search trees#

A binary tree is simply a tree where every node has at most two children, conventionally called left and right. That's the entire rule — no ordering requirement at all.

A binary search tree (BST) is a binary tree with one crucial extra rule that makes searching efficient: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. This ordering rule holds true recursively, at every single node, not just the root.

        8
       / \
      3   10
     / \    \
    1   6    14

Every value to the left of 8 (that's 3, 1, 6) is smaller than 8. Every value to the right (10, 14) is larger. And the same rule holds recursively — inside the left subtree, 1 is smaller than 3 and 6 is larger, and so on. This ordering is exactly what lets you search a BST the same way you'd binary search a sorted array: at each node, compare, then discard an entire half of the remaining tree.

A complete BST implementation#

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


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

    def insert(self, value):
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)

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

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

    def delete(self, value):
        self.root = self._delete_recursive(self.root, value)

    def _delete_recursive(self, node, value):
        if node is None:
            return None

        if value < node.value:
            node.left = self._delete_recursive(node.left, value)
        elif value > node.value:
            node.right = self._delete_recursive(node.right, value)
        else:
            # Found the node to delete — three cases:
            if node.left is None:
                return node.right          # no left child: promote right subtree
            if node.right is None:
                return node.left           # no right child: promote left subtree

            # Two children: find the smallest value in the right subtree
            # (the "in-order successor"), copy it into this node, then
            # delete that successor from the right subtree instead.
            successor = self._find_min(node.right)
            node.value = successor.value
            node.right = self._delete_recursive(node.right, successor.value)

        return node

    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node


bst = BinarySearchTree()
for value in [8, 3, 10, 1, 6, 14]:
    bst.insert(value)

print(bst.search(6))    # True
print(bst.search(99))   # False

bst.delete(3)            # deletes a node with two children (1 and 6)
print(bst.search(3))     # False
print(bst.search(1))     # True — 1 was correctly re-attached under the tree
print(bst.search(6))     # True

Insert and search both run in O(h), where h is the height of the tree — at each step, you discard an entire subtree, just like binary search discarding half an array. Deletion is the trickiest of the three: deleting a node with two children can't simply remove it (that would orphan its subtrees), so the standard trick is to replace its value with its in-order successor (the smallest value in its right subtree, found by walking left as far as possible) and then delete that successor instead — which is guaranteed to have at most one child, making it a simple case.

The four traversal methods#

"Traversal" means visiting every node in the tree in some defined order. There are four standard ways to do it, and each serves a different purpose.

In-order (left, node, right) — visits nodes in sorted order for a BST. This is the traversal you'll use most often when you specifically need a BST's contents sorted.

def in_order(node, result=None):
    if result is None:
        result = []
    if node is not None:
        in_order(node.left, result)
        result.append(node.value)
        in_order(node.right, result)
    return result

print(in_order(bst.root))   # [1, 6, 8, 10, 14] — sorted!

Pre-order (node, left, right) — visits the node itself before its children. Useful when you need to recreate the tree's structure (e.g., serializing a tree to save or transmit it), since the root always comes first.

def pre_order(node, result=None):
    if result is None:
        result = []
    if node is not None:
        result.append(node.value)
        pre_order(node.left, result)
        pre_order(node.right, result)
    return result

print(pre_order(bst.root))   # [8, 1, 6, 10, 14]

Post-order (left, right, node) — visits a node's children before the node itself. Useful whenever children need to be fully processed before their parent — for example, safely deleting an entire tree bottom-up, or evaluating an expression tree (evaluate both operands before applying the operator).

def post_order(node, result=None):
    if result is None:
        result = []
    if node is not None:
        post_order(node.left, result)
        post_order(node.right, result)
        result.append(node.value)
    return result

print(post_order(bst.root))   # [1, 6, 14, 10, 8]

Level-order (a.k.a. breadth-first) — visits nodes level by level, top to bottom, left to right within each level. Unlike the previous three (which are naturally recursive, following the call stack), this one uses a queue — exactly the structure covered on the previous page.

from collections import deque

def level_order(root):
    if root is None:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

    return result

print(level_order(bst.root))   # [8, 3, 10, 1, 6, 14] — level by level

When a BST degrades to O(n)#

Everything above assumed insert/search/delete run in O(h), and that h stays small — specifically, close to log n for n nodes, the same way a balanced binary search halves its search space every step. But nothing in the BST rules forces the tree to stay balanced. If you insert already-sorted data into a plain BST, every new node becomes the right child of the previous one, and the "tree" degenerates into what is really just a linked list:

skewed = BinarySearchTree()
for value in [1, 2, 3, 4, 5]:   # inserting in sorted order
    skewed.insert(value)

# The resulting tree is completely lopsided:
#   1
#    \
#     2
#      \
#       3
#        \
#         4
#          \
#           5

Here, the height h equals n, so search/insert/delete all degrade to O(n) — you've lost every benefit a tree was supposed to provide, and simply rebuilt a linked list with extra bookkeeping.

This is exactly the problem self-balancing trees exist to solve. Structures like the AVL tree and the Red-Black tree automatically perform rotations — local restructuring operations — after every insert or delete, to guarantee the tree's height never exceeds roughly O(log n), no matter what order data arrives in. You won't implement one by hand in this course (the rotation logic is intricate), but you should know, conceptually, exactly what problem they solve: they're what let real-world systems (many language runtimes' ordered maps/sets, database indexes) promise "search is O(log n)" as a guarantee, not just a hopeful average case.

Common mistakes#

• Assuming a BST always gives O(log n) performance. It only holds if the tree stays reasonably balanced — inserting pre-sorted data is a classic way to accidentally build a degenerate, linked-list-shaped tree.
• Confusing "binary tree" with "binary search tree." Every BST is a binary tree, but not every binary tree obeys the ordering rule — don't assume you can binary-search an arbitrary binary tree.
• Forgetting the two-children case in deletion is the tricky one. Directly removing a node with two children (without the in-order-successor swap) breaks the tree's structure — always replace-then-delete-the-successor instead.
• Mixing up traversal orders. It's easy to write "pre-order" when you meant "in-order" — if you need sorted output, in-order is the one you want; the mnemonic is simply "where does the node itself get appended relative to left and right?"