Tree Terminology & Representation

Stage 3: structures that branch

Every structure so far had one obvious "next" — arrays step to the next index, linked lists follow the single next pointer. A binary tree keeps the free-standing node from the linked-list module but gives each node two forward pointers instead of one: left and right. That single change — one pointer becomes two — is the whole leap from a line to a hierarchy, and it is why this module leans so heavily on recursion. The rest of this lesson makes the vocabulary precise (loose tree vocabulary is where most tree bugs are actually born) and then shows why the definition of a tree hands you the shape of every algorithm you will write on one.

The node

A binary-tree node is a value plus two child pointers, either of which may be null:

class TreeNode:
    def __init__(self, val: int = 0,
                 left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None) -> None:
        self.val = val
        self.left = left
        self.right = right

There is no separate "Tree" wrapper class the way LinkedList wrapped Node. A tree is a node — specifically its topmost node, the root. Hold the root and you hold the whole tree, because every other node is reachable by following left/right pointers down from it. This is the same "the structure is the pointers" idea from the linked-list module, now branching.

The vocabulary, stated precisely

These terms recur in every problem statement in this module; imprecise versions cause real off-by-one bugs, so pin them down:

• Root: the single node with no parent — the entry point.
• Child / parent: if p.left == c or p.right == c, then c is a child of p and p is the parent of c. In a tree every node has exactly one parent except the root, which has none. (That "exactly one" is what distinguishes a tree from a general graph.)
• Leaf: a node with no children — both left and right are null. Leaves are where recursion bottoms out.
• Internal node: any node that is not a leaf (has at least one child).
• Subtree: any node, taken together with all of its descendants, is itself a tree — a subtree of the original. The left subtree of a node is the whole tree rooted at its left child. This is not a figure of speech; it is literally true, and the next section shows why it matters.
• Depth of a node: the number of edges on the path from the root down to that node. The root has depth 0; its children have depth 1.
• Height of a node: the number of edges on the longest path from that node down to a leaf. A leaf has height 0. The height of the tree is the height of its root.
• Level: all nodes at the same depth form a level. Level 0 is just the root.

Depth counts down from the root to you; height counts down from you to the deepest leaf. They are measured from opposite ends, which is exactly why a later lesson (Top-Down vs. Bottom-Up Tree Recursion) has two different recursion shapes — one that carries depth downward and one that returns height upward.

A pitfall worth naming now: some sources define depth/height in terms of nodes on the path rather than edges, so a single-node tree has height 1 instead of 0. This course uses the edge count consistently. What matters is not which convention you pick but that you never mix them inside one algorithm — an unnoticed off-by-one between "nodes" and "edges" is a classic tree bug.

The recursive definition — and why it dictates the code

Here is the definition that the whole module rests on. A binary tree is one of exactly two things:

1. empty (represented by null), or
2. a node holding a value, whose left child is itself a binary tree and whose right child is itself a binary tree.

Read that again: the definition of a tree mentions trees. It is recursive — a tree is built out of smaller trees, bottoming out at the empty tree. This is not a convenient way to describe trees; it is what trees are.

The consequence is the single most useful fact in this module. Because the data is defined recursively, an algorithm over it can be defined the same way, and it will be both correct and short for the same structural reason:

To compute something about a tree, handle the empty case directly (the base case), otherwise combine the value at the node with the results of the same computation on node.left and node.right (the recursive case).

That template mirrors the definition line-for-line: the two cases of the data (empty / node-with-two-subtrees) become the two cases of the function (base case / recursive case). Here is the skeleton every recursive tree algorithm fills in:

def solve(node: TreeNode | None):
    if node is None:            # case 1: empty tree — the base case
        return base_value
    left = solve(node.left)     # same computation on the left subtree
    right = solve(node.right)   # same computation on the right subtree
    return combine(node.val, left, right)   # case 2: node with two subtrees

Why is this guaranteed to terminate and to be correct? Termination: each recursive call is on a strictly smaller tree (a proper subtree has fewer nodes than its parent tree), and you cannot shrink a finite tree forever — every path hits null. Correctness: if you assume the recursive calls return the right answer for the two subtrees (the induction hypothesis), and your combine step is right, then the whole thing is right by structural induction — the exact same induction the data's definition is built on. You are not "trusting the recursion" as an act of faith; the trust is licensed by the definition of the structure.

Almost everything in this module is this skeleton with different base_value and combine. Maximum depth, diameter, LCA, serialization — all of them are "handle null, recurse on both children, combine." Learning trees is largely learning what to put in those two blanks.

Why binary, and how it's stored

Two children (rather than three, or any number) is the common case because it is the minimum branching that still gives a hierarchy, and because two children map cleanly onto binary decisions — "less vs. greater" powers the binary search trees of the next module. General trees with arbitrary children exist (tries, in Module 20, are one), but the two-pointer node above is the workhorse.

Note that we store trees by pointers, exactly like linked lists — scattered node allocations wired together — not in a contiguous array. (A complete binary tree can be packed into an array with children of index i at 2i+1 and 2i+2; that trick is what makes heaps efficient in Module 19. For general-shaped trees it wastes too much space, so pointers win here.)

That O(h) stack cost is the hinge of the entire module: a balanced tree of n nodes has height ~log₂n, so recursion uses O(log n) stack, but a degenerate tree (every node has only a left child — effectively a linked list) has height n − 1, so recursion uses O(n) stack. Same node count, same O(n) time, wildly different space and stack-overflow risk.

The log₂n figure isn't asserted — it falls straight out of counting. A balanced tree fills each level before starting the next, and level i holds at most 2ⁱ nodes (1 at the root, 2 at level 1, 4 at level 2, and so on — each level's nodes are the children of the level above, and every node has 2 children). Summing a full tree of height h: n = 2⁰ + 2¹ + ⋯ + 2ʰ = 2ʰ⁺¹ − 1. Solving for h gives h = log₂(n + 1) − 1 — height grows only as the logarithm of the node count, because each additional level doubles how many more nodes it can hold. A degenerate tree gets no such multiplier — one child per node means each level adds exactly 1 node, so reaching n nodes takes n − 1 levels, not log₂n.

Picture the difference as two ways to grow a plant. A balanced tree is a bush: every branch splits into two more every time it grows, so a bush with a mere 10 layers of branching already has over a thousand twig-tips. A degenerate tree is a vine trained up a single pole: it gains exactly one node's worth of height per node, no splitting, so a thousand-node vine really is a thousand rungs tall. Same total amount of "plant," wildly different heights — which is exactly the O(log n) vs O(n) stack gap. The next lesson makes this concrete; Module 18 (balanced BSTs) exists mostly to guarantee the good case.