Trees, height and the vocabulary you need

A tree is a set of nodes with one root, where every other node has exactly one parent and no cycles. A binary tree limits each node to two children.

const node = (value, left = null, right = null) => ({ value, left, right });

//        1
//       / \
//      2   3
//     /
//    4
const root = node(1, node(2, node(4)), node(3));

The vocabulary

• Root — the node with no parent. Leaf — a node with no children.
• Depth of a node — edges from the root down to it.
• Height of a tree — the longest root-to-leaf path. A single node has height 0.
• Subtree — any node together with all of its descendants. This is the recursive definition that makes tree code short.

Shapes worth naming

Complete matters because it is exactly the shape a heap keeps, which lets a heap live in a flat array (chapter 11).

Height is the cost

Almost every tree operation walks one root-to-leaf path, so almost every cost is O(h):

• Balanced: h = log₂ n. A million nodes is 20 steps.
• Degenerate: h = n − 1. A million nodes is a million steps.

That gap between O(log n) and O(n) is the entire reason balanced trees exist. Quote tree complexity as O(h) and then state what h is for the shape in question — it shows you know the difference.

The recursive habit

Every node is the root of a subtree, so almost every tree algorithm has the same three-line shape:

function height(node) {
  if (!node) return -1;                                  // base case
  return 1 + Math.max(height(node.left), height(node.right));
}

Handle null, recurse into both children, combine. Get comfortable with that skeleton — the next four lessons are variations on it.