What are the root, an internal node and an external node (leaf) of a tree?
The root is the only node without a parent; an internal node has at least one child; an external node, or leaf, has no children.
* A is the root; B, C and F are internal; E, I, J, K, G, H and D are leaves; C with G and H forms a subtree. *
Every node of a tree falls into exactly one of these categories by counting its parent and its children:
| Term | Condition | In the example |
|---|---|---|
| Root | no parent | A |
| Internal node | at least one child | A, B, C, F |
| External node / leaf | no children | E, I, J, K, G, H, D |
The root is usually also internal. It counts as a leaf only in the degenerate tree with a single node.
The internal/external split matters for algorithms. Many recursive tree algorithms have their base case at the leaves (nothing below, so the answer is immediate) and their recursive case at internal nodes (combine the answers of the children). Height and expression evaluation both follow this pattern.