2.1Binary tree facts and formulas
The idea
A binary tree has simple counting laws: n nodes always have n − 1 edges, and the number of leaves is one more than the number of nodes with two children.
Think of it like this: A family tree: every person except the oldest has exactly one parent link.
Why it exists
Node and leaf counting questions are quick marks if you know the laws.
How it works
- edges = n − 1.
- n₀ = n₂ + 1 (leaves = two-child nodes + 1).
- Height h (edges): at most 2^(h+1) − 1 nodes and 2ʰ leaves.
- Full k-ary tree with i internal nodes: n = k·i + 1.
Worked example: A binary tree has 6 nodes with two children
Leaves = 6 + 1 = 7, whatever the number of one-child nodes.
Now play with it
- →Set n₂ = 6 in the calculator.
- →Change k and i to see a full ternary tree.
Catalan numbers: n = 1..8 give 1, 2, 5, 14, 42, 132, 429, 1430.
Check yourself
A full 3-ary tree has 10 internal nodes. How many leaves?
Exam notes (the dense version)
A binary tree with n nodes has n − 1 edges. With n₂ nodes of degree 2 and n₀ leaves: n₀ = n₂ + 1. Height h (edges) satisfies ⌈log₂(n + 1)⌉ − 1 ≤ h ≤ n − 1. A tree of height h has at most 2^(h+1) − 1 nodes and 2ʰ leaves. The number of distinct binary trees on n nodes is the Catalan number C(2n, n)/(n + 1).
Previous year questions: Trees & Binary Search Trees (15)
PYQs are grouped by topic, so this is the full set for Trees & Binary Search Trees; try the ones that match this subtopic. Open all 15 on the topic page.