Trees — the basics

The data structure behind file systems, HTML, and org charts — a natural extension of the linked list, once "each node points to one next thing" becomes "each node points to several children."

Beginner

4 min read

A tree is a linked list that's allowed to branch

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
 
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)

A linked list node points to exactly one "next" node. A tree node can point to several — in a binary tree specifically, exactly two, conventionally called left and right. This single change (one next-pointer becomes several child-pointers) is the entire structural difference; everything else about trees is a consequence of that one change. The vocabulary: the topmost node is the root, a node with no children is a leaf, and a node's left/right connections are its children.

Why trees model so many real things naturally

A file system is a tree — a folder contains files and other folders, which contain more files and folders, arbitrarily deep. HTML is a tree — a <div> contains other elements, which contain more elements. An org chart is a tree — a manager has direct reports, who have their own direct reports. Any "this thing contains other things of the same kind, potentially nested arbitrarily deep" relationship is naturally a tree — which is exactly why trees show up constantly in real software, not just as an interview topic.

Binary search trees: a tree with an ordering rule

A binary search tree (BST) adds one specific rule: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. This ordering rule is what makes searching a BST fast — at each node, comparing the target value tells you which entire subtree to search next and which to ignore completely, the same "eliminate half the remaining space" idea the binary search lesson covers, just expressed as a tree's shape instead of an array. Searching a balanced BST is O(log n), for exactly the same underlying reason binary search on a sorted array is.

Traversal: visiting every node, in a defined order

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

In-order traversal (left subtree, then this node, then right subtree) visits a binary search tree's values in sorted order — a direct consequence of the BST ordering rule above. This recursive shape — "process the left side, do something with this node, process the right side" — is the tree equivalent of the linked-list traversal pattern from its own lesson, just branching into two recursive calls instead of one loop step. Pre-order (node, then left, then right) and post-order (left, then right, then node) are the same idea with the node's own processing step moved to a different position, each useful for different situations — pre-order for copying a tree's structure, post-order for safely deleting a tree bottom-up.

Depth-first vs. breadth-first, on a tree specifically

The in-order/pre-order/post-order traversals above are all depth-first — they follow one branch all the way down before backing up to try another, using the call stack (or an explicit stack) to do it, exactly the DFS behavior covered in an earlier DSA flashcard. Visiting a tree level by level instead (root, then all of its children, then all of their children) is breadth-first (BFS), and it uses a queue instead of a stack — the same stack-vs-queue distinction the previous lesson covers, applied directly to tree traversal.

Why "balanced" matters for a BST's speed guarantee

A binary search tree's O(log n) search speed assumes the tree is roughly balanced — each subtree is roughly similar in size. Inserting already-sorted values one at a time into a naive BST (with no rebalancing) produces exactly the degenerate shape above — every node has only a right child, no left — which is structurally just a linked list wearing a tree's name, with O(n) search instead of O(log n). Real-world tree implementations that need a real speed guarantee (like a database index's B-tree, covered in the system design domain) actively rebalance themselves as data is inserted, specifically to avoid this collapse.