Special Types of Binary Trees and Their Properties
Special Types of Binary Trees
A binary tree is a tree where each node can have at most two children. But not all binary trees look the same. Some of them follow special rules about how their nodes are arranged. When a tree follows a clear rule, it becomes easier to study, easier to reason about, and often more useful for solving real problems. So we give these special trees names. Let's meet the most important ones.
Before we start, two quick words you'll see again and again:
- An internal node is a node that has at least one child (a "parent" inside the tree).
- A leaf node is a node with no children at all (the very ends of the tree).
The height of a tree is the number of steps on the longest path from the top node (the root) down to the deepest leaf. A single lonely node has height 0.
Full Binary Tree
A full binary tree (also called a proper binary tree) follows one simple rule: every node has either two children or no children. No node is allowed to have just one child.
Think of it like a strict family rule: you either have two kids or none — never an only child.
A single node by itself is the smallest full binary tree (height 0). A root with two leaves is a full binary tree of height 1. As long as every parent has exactly two children, the tree stays "full."
Full binary trees have some neat number patterns. If you count the nodes, these always hold true:
- Number of leaf nodes = number of internal nodes + 1
- Total number of nodes = 2 × (number of internal nodes) + 1
- Number of internal nodes = (total number of nodes − 1) / 2
- Number of leaves = (total number of nodes + 1) / 2
- Total number of nodes = 2 × (number of leaf nodes) − 1
- Number of internal nodes = number of leaf nodes − 1
- Maximum number of leaves = 2 ^ height
The key takeaway: in a full binary tree there is always exactly one more leaf than internal nodes. If you know any one count, you can work out all the others.
Complete Binary Tree
A complete binary tree has all its levels completely filled, except possibly the last level. And the last level must be filled from left to right, with no gaps.
Imagine filling seats in a theater row by row. You fill the front row completely before starting the next row, and within a row you always sit people starting from the left. You never leave an empty seat with someone sitting to its right. That is exactly how a complete binary tree fills up.
This "left to right, no holes" rule is why complete binary trees are so handy in practice — they pack tightly and can be stored neatly inside an array.
Perfect Binary Tree
A perfect binary tree is the most symmetric of all. In it:
- Every internal node has exactly two children, and
- All leaf nodes sit at the same level (the bottom is perfectly flat).
A perfect binary tree of height 2 is a full triangle: 1 root, 2 nodes below it, then 4 leaves — every level completely full.
Notice that a perfect tree is also full *and* complete. It's the "best of both" shape. Because it is so regular, its counts follow exact formulas:
- Total number of nodes = 2 ^ (height + 1) − 1
- Height = log(n + 1) − 1
- Number of leaf nodes = 2 ^ height
For example, a perfect tree of height 2 has 2 ^ (2 + 1) − 1 = 7 nodes, with 2 ^ 2 = 4 leaves at the bottom.
Skew Binary Tree
A skew binary tree is the opposite of balanced. Every internal node has only one child. So the tree leans to one side like a tilted ladder, going down in a single line.
If every node leans right, it's a *right-skewed* tree; if every node leans left, it's *left-skewed*. A skew tree of height 2 is just three nodes in a slanted line. It looks less like a tree and more like a linked list — which is exactly why it's usually the *worst* shape for performance.
Quick Comparison
| Tree type | The rule |
|-----------|----------|
| Full | Each node has 2 children or 0 |
| Complete | All levels full except the last, filled left to right |
| Perfect | Every internal node has 2 children AND all leaves at same level |
| Skew | Each internal node has exactly 1 child |
