Data Structures: Trees, Binary Search Trees, and Tree Traversal

Post #4’s hash tables are genuinely excellent at one specific job — retrieve a value instantly, given its exact key — and genuinely bad at a different, equally common job: retrieve everything in sorted order, or find everything between two values. A hash table has no inherent notion of order at all; the hash function’s entire purpose is to scatter keys unpredictably across an array for speed. Trees are the structure built specifically for the ordering and hierarchy hash tables give up.

Trees: Hierarchical Structure

A tree organizes data hierarchically — one root node at the top, with each node having zero or more children, and every node except the root having exactly one parent. This is a genuinely different relationship than the linear sequences covered in Post #3 (arrays, linked lists) — it directly models anything with a natural hierarchy: a file system’s folders and subfolders, an organization chart, or — a structure you have already worked with directly, in this blog’s JavaScript series — the DOM, covered in that series’ Post #10, which is precisely a tree of HTML elements, each with a parent and any number of children.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)


root = TreeNode("Documents")
photos = TreeNode("Photos")
work = TreeNode("Work")
root.add_child(photos)
root.add_child(work)

Binary Trees: At Most Two Children

A binary tree restricts each node to at most two children, conventionally called left and right.

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

This restriction is not arbitrary — it enables the specific, powerful structure covered next.

Binary Search Trees: Ordering Built Into the Structure

A Binary Search Tree (BST) is a binary tree with one additional, defining rule: for every node, every value in its left subtree is smaller, and every value in its right subtree is larger. This ordering property, maintained consistently throughout the entire tree, is what makes search genuinely efficient.

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

    def insert(self, value):
        if value < self.value:
            if self.left is None:
                self.left = BSTNode(value)
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BSTNode(value)
            else:
                self.right.insert(value)

    def search(self, value):
        if value == self.value:
            return True
        elif value < self.value:
            return self.left.search(value) if self.left else False
        else:
            return self.right.search(value) if self.right else False


root = BSTNode(50)
for value in [30, 70, 20, 40, 60, 80]:
    root.insert(value)

print(root.search(40))  # True
print(root.search(45))  # False

Why search is efficient: at every single node, comparing the target value against the current node’s value eliminates an entire subtree from consideration — exactly as if you always knew which half of a sorted list to search next, without checking the other half at all. For a reasonably balanced tree, this produces logarithmic-time search — dramatically fewer comparisons than checking every value one by one, formally covered once Post #7 introduces Big O notation directly.

The Four Ways to Traverse a Tree

Visiting every node in a tree, in a specific, useful order, is called traversal — and there are four standard approaches, each producing a genuinely different, useful result.

In-Order Traversal: Left, Node, Right

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

print(in_order(root))  # [20, 30, 40, 50, 60, 70, 80] — SORTED order!

For a binary search tree specifically, in-order traversal always visits every value in fully sorted order — a direct, elegant consequence of the BST’s defining ordering property.

Pre-Order Traversal: Node, Left, Right

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

Useful specifically for creating a copy of a tree’s exact structure, or serializing a tree to be reconstructed later — the root is recorded first, before either subtree.

Post-Order Traversal: Left, Right, Node

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

Useful specifically when children must be fully processed before their parent — safely deleting an entire tree node by node, for instance, or evaluating a mathematical expression tree where operands must be computed before the operator combining them.

Breadth-First (Level-Order) Traversal: One Level at a Time

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:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

print(level_order(root))  # [50, 30, 70, 20, 40, 60, 80]

This is genuinely different from the previous three — rather than diving deep down one branch before backtracking, it explores the tree one entire level at a time, using exactly the queue covered in Post #3, directly setting up the identical technique Post #6 applies to graph traversal.

When a BST Stops Being Efficient

If values are inserted in an already-sorted order, a BST degenerates into something structurally identical to a linked list — every node has only a right child (or only a left child), and the efficient “eliminate half the tree” search advantage disappears entirely.

degenerate_root = BSTNode(1)
for value in [2, 3, 4, 5]:  # already sorted — the worst case for a naive BST
    degenerate_root.insert(value)
# This tree is now, structurally, just a linked list wearing a tree's clothing

This is precisely the motivation for self-balancing trees (AVL trees, red-black trees, and similar) — structures that automatically restructure themselves during insertion to guarantee the tree stays reasonably balanced, preserving the efficient search property regardless of insertion order. Full coverage of self-balancing techniques is beyond this introductory post’s scope, but knowing the problem they solve — and precisely why it matters — is the genuinely important takeaway here.

Real-World Use Cases

The DOM: Directly referenced above — every webpage’s structure, covered in this blog’s JavaScript series, is a tree exactly as covered in this post, with document.body as a root-adjacent node and every nested element a child.

File systems: Folders containing files and subfolders form a natural tree, with traversal algorithms directly analogous to this post’s coverage used to search or list an entire directory structure.

Database indexes: Many database indexes, covered fully once Post #14 addresses databases directly, use tree-based structures (commonly a variant called a B-tree) specifically for their efficient range-query and sorted-order capabilities that hash tables cannot provide.

Autocomplete and prefix search: Specialized tree variants (tries) build directly on this post’s tree concepts to enable extremely fast “find all words starting with this prefix” functionality.

Common Mistakes and Gotchas

⚠️ Mistake 1: Assuming any binary tree is a binary search tree A binary tree is simply “at most two children per node” — the BST’s specific left-smaller, right-larger ordering property is an additional, separate rule, not an automatic consequence of being a binary tree at all.

⚠️ Mistake 2: Inserting sorted data into a naive BST without balancing Covered directly above — this produces the degenerate, linked-list-like worst case, silently losing the entire efficiency advantage a BST is meant to provide.

⚠️ Mistake 3: Confusing traversal order names “In-order,” “pre-order,” and “post-order” refer specifically to when the current node itself is visited relative to its children (before both, between them, or after both) — mixing these up produces a traversal that runs without error but visits nodes in the wrong order for your actual purpose.

⚠️ Mistake 4: Using recursive traversal on an extremely deep, unbalanced tree Each recursive call (covered fully in Post #10) adds a frame to the call stack referenced in Post #3 — an extremely deep, degenerate tree can exhaust available stack space; an iterative traversal using an explicit stack or queue, as level-order traversal demonstrates, avoids this risk.

Quick Reference

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

# BST property: left < node < right, recursively, at every node

# Traversal orders
# In-order:    Left, Node, Right  → sorted order for a BST
# Pre-order:   Node, Left, Right  → useful for copying/serializing
# Post-order:  Left, Right, Node  → useful for safe deletion
# Level-order: breadth-first, using a queue → one level at a time

Exercises

Exercise 1 — Direct application Extend the BSTNode class from this post with a find_min() method that returns the smallest value in the tree — think about which direction to always move.

Exercise 2 — Slight variation Write a function tree_height(node) -> int that returns the height of a binary tree (the number of edges on the longest path from root to a leaf), using recursion.

Exercise 3 — Real-world combination Write a function that takes a plain Python list and inserts every value into a BST, then uses in-order traversal to return a fully sorted version of the list — a genuine, working sorting algorithm built entirely from this post’s concepts.

Exercise 4 — Open-ended challenge Deliberately create a degenerate BST by inserting values 1 through 1000 in already-sorted order, then time how long a search for the value 999 takes compared to a search in a BST built from the same values inserted in random order.

FAQ

Q: Is a BST always faster than a hash table for lookups? A: No — for a pure “look up by exact key” operation, a hash table’s average O(1) beats a balanced BST’s O(log n). A BST earns its place specifically when you also need sorted-order traversal or range queries, which a hash table cannot provide at all.

Q: What’s the difference between “tree” in computer science and a family tree? A: Structurally similar in spirit — hierarchical, parent-child relationships — though a genuine family tree can have a node (a child) with two parents, which technically makes it a different structure (closer to a graph, covered in Post #6) than the strict single-parent trees covered in this post.

Q: Why do I need four different traversal orders instead of just one? A: Each serves a genuinely different purpose, covered directly throughout this post — sorted output, structural copying, safe deletion, and level-by-level processing are different tasks, and each traversal order is specifically suited to one of them.

Q: Do I need to implement self-balancing trees myself in real projects? A: Rarely — most languages’ standard libraries or well-established packages provide balanced tree implementations (or, more commonly in practice, you would reach for a database’s built-in indexing, covered in Post #14) rather than hand-rolling a self-balancing tree from scratch for typical application needs.

Summary and Next Steps

You now understand trees as the structure built specifically for the hierarchy and ordering hash tables deliberately give up — binary search trees’ left-smaller, right-larger property enabling efficient search, the four traversal orders each suited to a different task, and the genuine risk of a naive BST degenerating into linked-list-like worst-case performance when balance is not maintained.

Your next step: Complete Exercise 3 — building a working sort from BST insertion and in-order traversal — since seeing a genuine, useful algorithm emerge directly from combining this post’s concepts is considerably more convincing than treating trees as abstract theory disconnected from practical results.

Last updated: August 2026.