Internal vs External Nodes
You'll learn how to distinguish between nodes that have children (internal) and nodes that don't (external/leaves), plus an important counting relationship between them.
What Are Internal and External Nodes?
In any tree structure, nodes fall into two categories based on whether they have children:
- Internal nodes (also called non-leaf nodes) have at least one child. These include the root if it has children.
- External nodes (also called leaves) have zero children. They sit at the "edges" of your tree.
Think of a family tree: internal nodes are people with descendants in the tree, while external nodes represent the youngest generation shown—no children recorded below them.
Visualizing the Difference
A <- internal (has children)
/ \
B C <- both internal (have children)
/ \ \
D E F <- all external/leaves (no children)
Here, A, B, and C are internal nodes. D, E, and F are external nodes.
The Counting Relationship
In a proper binary tree (where every internal node has exactly 0 or 2 children), there's a beautiful formula:
Number of external nodes = Number of internal nodes + 1
Or: E = I + 1
Why? Each internal node "creates" two connection points (for its two children). As you build the tree, you're essentially converting external nodes into internal ones while adding new external nodes. The math works out so leaves always outnumber internal nodes by exactly one.
In the example above: 3 external nodes, 2 internal nodes. 3 = 2 + 1 ✓
Key Takeaway: Internal nodes have children and drive tree structure, while external nodes (leaves) mark endpoints. In proper binary trees, there's always exactly one more leaf than internal node.