Tree terminology and shape

A handful of words show up in every tree problem. Pin them down now.

Root — the single top node, with no parent.
Leaf — a node with no children (both Left and Right are nil).
Parent / child — a node points down to its children; each non-root node has exactly one parent.
Edge — the link between a parent and a child.
Depth of a node — the number of edges from the root down to it. The root has depth 0.
Height of a tree — the number of edges on the longest root-to-leaf path. A single node has height 0; an empty tree is usually given height -1.
Level — all nodes at the same depth. Level 0 is just the root.

Shape matters

The same set of values can form very different trees:

    2            1
   / \            \
  1   3            2
                    \
                     3

The left tree is balanced — its height is small (≈ log n) relative to the number of nodes. The right one is degenerate: every node has a single child, so it's really a linked list wearing a tree costume, height n − 1. Operations that should be O(log n) on a balanced tree degrade to O(n) on a degenerate one.

Counting work

Most algorithms in this section visit every node once, so they run in O(n) time. The extra space is the recursion depth — O(h), where h is the height. That's O(log n) for a balanced tree but O(n) for a degenerate one. Keep height in mind: it governs the memory a recursive traversal uses.

Next: the two fundamental ways to visit those nodes.