Tree fundamentals

A tree is a graph with two additional constraints: it is connected (there is a path between every pair of nodes) and acyclic (there are no cycles). Together these constraints mean there is exactly one path between any two nodes. Remove one edge and the tree splits into two pieces. Add one edge and you create a cycle.

Trees are everywhere in computing. File systems are trees. HTML documents are trees. The call stack of a recursive function traces a path through an implicit tree. Syntax parsers produce trees. Many database indexes are trees.

Binary trees

A binary tree is a rooted tree where each node has at most two children, conventionally called left and right. The node at the top is the root. Nodes with no children are leaves.

         4          ← root
        / \
       2   6
      / \ / \
     1  3 5  7      ← leaves

Key vocabulary:

• Height of a node — the number of edges on the longest path from that node down to a leaf. The height of the tree is the height of the root.
• Depth of a node — the number of edges from the root to that node.
• Subtree — a node plus all its descendants. Every node is the root of its own subtree.

A tree of height h can hold at most 2^(h+1) − 1 nodes if perfectly balanced. That exponential relationship is why balanced trees enable O(log n) operations: at each node you can eliminate an entire subtree from consideration.

Traversal orders

To "traverse" a tree means to visit every node exactly once in a defined order. For a binary tree, three recursive orders are standard, each defined by when you visit the root relative to its subtrees.

Inorder: left → root → right

Visit the entire left subtree, then the root, then the entire right subtree. For the tree above: 1, 2, 3, 4, 5, 6, 7 — sorted order. This is not a coincidence: the BST invariant (covered in the next lesson) guarantees that inorder traversal of a binary search tree always produces values in ascending order.

Preorder: root → left → right

Visit the root first, then recurse left, then recurse right. For the tree above: 4, 2, 1, 3, 6, 5, 7. Preorder is "copy-friendly" — if you reconstruct a tree by inserting nodes in preorder, you recreate the original structure exactly.

Postorder: left → right → root

Visit both subtrees before the root. For the tree above: 1, 3, 2, 5, 7, 6, 4. Postorder is "deletion-friendly" — you process children before parents, so you can safely free or aggregate child data before touching the parent. Expression evaluators and directory-size calculators use postorder for this reason.

Trees as restricted graphs

Because a tree is a graph, all graph algorithms apply. BFS on a tree produces a level-order traversal (all nodes at depth 1, then depth 2, and so on). DFS on a tree, depending on whether you process the node before or after recursing, gives preorder or postorder. Inorder has no direct equivalent in general graphs — it is specific to binary trees.

The absence of cycles removes the need for a visited set when traversing a tree: you will never loop back to a node you have already seen, because there is only one path to any node.

Where to go next

Next: tree traversals — implement TreeNode, write inorder, preorder, and postorder traversal functions, and compute tree height in Python.