When a list is the wrong shape

Every structure so far has been flat. A list of students, a row of buckets, a stack of plates. But a great deal of real data is not flat.

A file system. A comment with replies, which have replies. A company where everyone has one manager and some people have reports. None of these fit in a line, and forcing them into one loses the thing that mattered.

The shape

A tree is nodes connected so that each node has exactly one parent, except one node with none, called the root. No cycles, and exactly one path between any two nodes.

            CEO
           /   \
        Head    Head
        /  \      \
     Dev   Dev    Sales

A node with no children is a leaf. The height is the longest path from the root down to a leaf, and height is what decides performance, because most tree operations walk one path from the root.

Binary trees

A binary tree limits each node to at most two children, called left and right. That restriction is what makes the code short:

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

Walking it

There are three depth first orders, and they differ only in when the node itself is handled relative to its children.

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

The recursion is the shape of the structure. A tree is defined in terms of smaller trees, so a function on a tree calls itself on smaller trees, and the base case is the empty one.

There is also level order, which visits row by row and needs a queue rather than recursion. It is the same breadth first search that graphs use two pages from now.

Why height matters

A tree of n nodes can have height as low as about log n, if it is full and balanced, or as high as n, if every node has one child and it is really a linked list wearing a hat. Every operation that walks a path costs the height, so that difference is the whole story of the next page.