[Intermediate] — the tree this course is built on, and the five shapes worth naming.
Before you start
- You know the tree vocabulary — root, parent, child, leaf, subtree, height, depth — from trees.
- You can trace a recursive function.
After this lesson you will be able to:
- Define a binary tree and write the node class it is built from.
- Name and recognise the five standard shapes: full, complete, perfect, degenerate and balanced.
- Implement a check for each shape, and say which property each one guarantees.
- Explain why complete binary trees can be stored in a flat array with no pointers.
Study route: read the shapes, then the implementations, then the array-storage section at the end.
What a binary tree is
A binary tree is a tree in which every node has at most two children. They are named the left child and the right child, and the distinction matters — swapping them gives a different tree, even with the same values present.
That is the whole definition. There is no rule about the values, no ordering requirement and no balance requirement. Those come later: ordering is what makes a binary search tree, and balance is what makes it fast.
A Binary Tree is the most widely used variation of a tree. The rule is simple: Every node can have AT MOST two children, conventionally named left and right.
The node
class TreeNode:
"""Represents a single node in a Binary Tree."""
def __init__(self, val=0, left=None, right=None):
self.val = val # The value stored in this node
self.left = left # Reference to left child (TreeNode or None)
self.right = right # Reference to right child (TreeNode or None)The five shapes
Understanding these shapes is critical because a tree’s shape directly dictates its performance ( vs ).
1. Full (Proper) Binary Tree
Every node has either 0 or 2 children. No node has only 1 child.
1
/ \
2 3
/ \
4 5
Where it’s used: Arithmetic expression trees (e.g. (4 + 5) * 3), where operators (+, *) take 2 operands, and numbers take 0.
2. Complete Binary Tree
Every level is completely filled, except possibly the last level, which is filled strictly from left to right.
1
/ \
2 3
/ \ /
4 5 6
Where it’s used: Heaps and Priority Queues! Because there are no gaps, a complete binary tree can be stored efficiently in a flat Array without using pointers.
3. Perfect Binary Tree
All internal nodes have 2 children, and all leaves are at the exact same depth.
1
/ \
2 3
/ \ / \
4 5 6 7
Formula: A perfect binary tree of height has total nodes . For height 2, nodes.
4. Balanced Binary Tree
A tree where the height of the left and right subtrees of every node differs by at most 1.
1
/ \
2 3
/
4
Why it matters: Keeps tree height bounded to , guaranteeing fast searches.
5. Degenerate (Pathological) Binary Tree
Every node has only 1 child. The tree degrades into a single straight line.
1
\
2
\
3
\
4
Why it’s dangerous: Structurally identical to a Linked List. Height becomes , and operations slow down from to .
Implementing the shape checks
Each shape is a property you can test for. These are written to be read rather than run — there is no lab here, because each one is short enough to follow by eye, and the point is the definition made precise, not a measurement.
All of them assume the node class above.
Full binary tree
A node is full if it has either zero or two children — never exactly one.
def is_full(node):
"""Every node has 0 or 2 children, never 1."""
if node is None:
return True # an empty tree is vacuously full
if (node.left is None) != (node.right is None):
return False # exactly one child: not full
return is_full(node.left) and is_full(node.right)Perfect binary tree
Every internal node has two children and every leaf sits at the same depth. The neat way to check it is by the numbers: a perfect tree of height has exactly nodes, and no other shape does.
def height(node):
"""Edges on the longest downward path. An empty tree is -1 by convention,
so a single node comes out as 0."""
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def count_nodes(node):
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
def is_perfect(node):
"""A perfect tree of height h has exactly 2^(h+1) - 1 nodes."""
h = height(node)
return count_nodes(node) == (2 ** (h + 1)) - 1Complete binary tree
Every level is full except possibly the last, and the last fills strictly left to right. The clean check uses a level-order walk: once you have seen a gap, you must never see another node.
from collections import deque
def is_complete(root):
"""Level-order walk. After the first missing child, everything must be missing."""
if root is None:
return True
queue = deque([root])
seen_gap = False
while queue:
node = queue.popleft()
if node is None:
seen_gap = True # from here on, only gaps are allowed
else:
if seen_gap:
return False # a real node AFTER a gap: not complete
queue.append(node.left)
queue.append(node.right)
return TrueBalanced binary tree
For every node, the heights of its two subtrees differ by at most one. The naive version recomputes heights and costs ; this one returns the height and a sentinel together, so it is one pass and .
def is_balanced(root):
"""True if every node's subtrees differ in height by at most 1.
The helper returns -2 as a sentinel meaning 'already unbalanced below here',
so the whole check is a single pass rather than height() called repeatedly."""
def check(node):
if node is None:
return -1
left = check(node.left)
if left == -2:
return -2
right = check(node.right)
if right == -2:
return -2
if abs(left - right) > 1:
return -2
return 1 + max(left, right)
return check(root) != -2Degenerate binary tree
Every node has at most one child, so the tree is a linked list wearing a tree’s clothes.
def is_degenerate(node):
"""Every node has at most one child."""
if node is None:
return True
if node.left is not None and node.right is not None:
return False
return is_degenerate(node.left) and is_degenerate(node.right)Why complete trees can live in an array
This is the most useful consequence of any of these shapes, and it is why heaps are built on complete trees.
Because a complete tree has no gaps except at the end, you can number the nodes level by level, left to right, and store them in a flat array at exactly those positions. The relationships then become arithmetic:
- The left child of the node at index is at index .
- The right child is at index .
- The parent is at index .
A(0) array: [A, B, C, D, E, F]
/ \ index: 0 1 2 3 4 5
B(1) C(2)
/ \ / left child of B (index 1) is at 2(1)+1 = 3 -> D
D(3) E(4) F(5) parent of E (index 4) is at (4-1)//2 = 1 -> B
No pointers are stored at all. That saves the memory two references per node would cost, and it puts the whole tree in one contiguous block, so walking it is cache-friendly in a way a pointer-based tree never is.
The catch is that it only works while the tree stays complete. Put a gap in the middle and the arithmetic breaks, because every later position shifts. That is exactly why a heap keeps itself complete by construction — inserting always adds at the next free array slot and removing always takes the last one — while a binary search tree, whose shape is dictated by the order keys arrive in, cannot be stored this way without wasting most of the array.
Common pitfalls and traps
- Confusing full with complete. Full is about the number of children — 0 or 2. Complete is about where the gaps are — only at the end of the last level. A tree can be either one without being the other.
- Assuming “binary tree” implies ordering. It does not. Ordering is the extra rule that makes a binary search tree. A heap and an expression tree are both binary and neither is sorted.
- Treating left and right as interchangeable. They are not. Two trees holding the same values in mirrored positions are different trees, and an in-order traversal will show it.
- Using the naive balance check. Calling
height()from inside a recursive balance check recomputes the same subtree heights over and over, costing . The sentinel version above is . - Forgetting the empty-tree convention. Here
height(None)is , so a single node has height . Some books use for empty and for a single node. Neither is wrong, but mixing the two produces off-by-one errors everywhere.
Check your understanding
- How many nodes does a perfect binary tree of height 3 have?
- Is a perfect tree always complete? Is a complete tree always perfect?
- Give a tree that is full but not complete.
- Why can a heap be stored in an array, while a general binary search tree usually cannot?
- A node sits at index 10 in an array-stored complete tree. Where are its children and its parent?
Answers — open only after an attempt
- nodes.
- Yes to the first: a perfect tree has every level full, which satisfies completeness. No to the second: a complete tree may have a partly-filled last level, which a perfect tree may not.
- A root with two children, where the left child has two children of its own and the right child has none. Every node has 0 or 2 children, so it is full. But the last level has nodes on the left and nothing under the right child while the level above is not full, so it is not complete.
- Because a heap is kept complete by construction — insertions go at the next free array slot and removals take the last one, so there are never gaps in the middle. A binary search tree’s shape is dictated by the order its keys arrive in, so gaps appear in arbitrary places and the index arithmetic would leave most of the array empty.
- Children at and . Parent at .
Before moving on
You can define a binary tree, name and check all five shapes, and explain array storage.
Recap: a binary tree allows at most two children, named left and right, and which is which matters; full means 0 or 2 children everywhere; perfect means full and every leaf at the same depth, with exactly nodes; complete means every level full except the last, which fills left to right; balanced means subtree heights differ by at most one at every node; degenerate means at most one child everywhere, which is a linked list. A complete tree stores in a flat array with children at and and parent at .
Next: Binary Search Trees — what happens when you add an ordering rule.
Related
- Trees — the vocabulary, and the other kinds of tree
- Binary Search Trees — the next lesson
- Heaps — built on a complete binary tree, stored in an array
- Traversal — how to visit every node
Software engineering
Infrastructure & security
Computer science
Hardware & engineering