Trees

A tree stores data that branches, like folders inside folders or a family tree. It's made of nodes again, but each node can point to several children. The top node is the root, nodes with no children are leaves, and how many steps a node sits below the root is its depth.

In a binary tree each node has at most two children, left and right. A binary search tree (BST) adds one rule: everything in a node's left branch is smaller than it, and everything in its right branch is bigger.

        8
      /   \
     3     10
    / \      \
   1   6      14

That rule makes searching quick. To find 6, start at the root: 6 is less than 8, go left; more than 3, go right; found. Each step throws away a whole branch. A balanced tree with a million items is only about 20 levels deep, so a search takes about 20 steps.

Going through every node is called a traversal. An in-order traversal (left branch, then the node, then the right branch) visits a BST's values in sorted order.

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

tree = (8, (3, (1, None, None), (6, None, None)), (10, None, (14, None, None)))
print(in_order(tree))

If you add values already in order (1, 2, 3, 4…), a plain BST leans into one long line and loses its speed. Self-balancing trees (red-black trees, AVL trees) rotate nodes to stay bushy, and databases use wide relatives called B-trees.