Types of Binary Trees: Full, Complete, Perfect and Balanced

A binary tree is simple to define: every node has at most two children, a left one and a right one. The vocabulary built on top of it is where people stumble. "Full", "complete", "perfect" and "balanced" sound like synonyms; they are not, and interview questions depend on the difference: a heap must be complete, a search tree is fast only when balanced, and "check whether this tree is complete" is a question in its own right. This article defines each type, tests for it, and checks the tests against every small tree shape.

The problem it solves

The shape of a tree decides what you can do with it:

• Height decides speed. Searching, inserting and deleting in a binary search tree cost O(h), where h is the height. A balanced tree keeps h near log₂ n; a degenerate one lets it reach n - 1.
• Completeness decides storage. A complete tree fits in an array with no gaps, which is exactly how binary heaps are stored.
• Fullness and perfection give counting formulas for proofs and quick sanity checks.

The intuition

Start from the lesson's definition. Each node has two child slots, left and right; either may be empty (None in Python), and the two are positions, not an unordered pair, so swapping them makes a different tree. With that in place, the five named shapes are:

• Full (also called proper or strict): every node has zero or two children, never one. In any full tree, leaves outnumber internal nodes by exactly one.
• Complete: every level is full except possibly the last, and the last level is filled from the left with no gaps. Number the nodes level by level from 0, and a complete tree with n nodes uses exactly the numbers 0 to n - 1; node i has its children at 2i + 1 and 2i + 2.
• Perfect: every internal node has two children and every leaf sits on the same level. A perfect tree of height h has exactly 2^(h+1) - 1 nodes.
• Balanced (height-balanced): at every node, the heights of the two subtrees differ by at most one. This is the property that keeps height at O(log n), and the one AVL trees maintain.
• Degenerate: every internal node has one child. It is a linked list wearing a tree's clothes, with height n - 1.

The types nest: every perfect tree is full, complete and balanced, and every complete tree is balanced, but neither a full nor a balanced tree need be complete. Textbooks disagree on names, and some older ones say "complete" for what is called perfect here, so in an interview, state your definition before you code.

Watch it run

The animation uses the lesson's tree, 1 with children 2 and 3, and 4 and 5 under 2. A binary node has exactly two child slots, left and right, never three. Node 2 fills both of its slots, 4 on the left and 5 on the right. Node 3 fills neither: both slots exist and both hold None. Swap 4 and 5 and this is a different tree; the two slots are positions, not an unordered pair. Put them back, and counting the tree is one line of recursion, where an empty slot contributes 0. The count returns in postorder: each real node returns 1 + left + right, 3 returns 1 + 0 + 0 = 1 because both its children are empty, and five nodes, each visited once, give count(root) = 5. That tree is full, complete and balanced, but not perfect: 3's slots are empty while 2's are not.

The code

One test per type. The completeness test walks level by level and fails if a real node ever appears after an empty slot; balance is checked in one post-order pass that returns None as soon as any subtree is unbalanced:

from collections import deque

class Node:
    def __init__(self, v, l=None, r=None):
        self.val, self.left, self.right = v, l, r

def count(n):
    return 0 if n is None else 1 + count(n.left) + count(n.right)

def height(n):
    return -1 if n is None else 1 + max(height(n.left), height(n.right))

def is_full(n):
    if n is None:
        return True
    if (n.left is None) != (n.right is None):        # exactly one child
        return False
    return is_full(n.left) and is_full(n.right)

def is_complete(root):
    q, seen_gap = deque([root]), False
    while q:
        node = q.popleft()
        if node is None:
            seen_gap = True                          # every slot after this must be empty
        elif seen_gap:
            return False
        else:
            q.extend([node.left, node.right])
    return True

def is_perfect(root):
    return count(root) == 2 ** (height(root) + 1) - 1

def is_balanced(root):
    def check(n):                                    # height, or None if unbalanced below
        if n is None:
            return -1
        l, r = check(n.left), check(n.right)
        if l is None or r is None or abs(l - r) > 1:
            return None
        return 1 + max(l, r)
    return check(root) is not None

def kinds(root):
    return [name for name, test in [("full", is_full), ("complete", is_complete),
            ("perfect", is_perfect), ("balanced", is_balanced)] if test(root)]

lesson = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(count(lesson), height(lesson), kinds(lesson))
# 5 2 ['full', 'complete', 'balanced']
print(kinds(Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))))
# ['full', 'complete', 'perfect', 'balanced']
print(kinds(Node(1, Node(2, None, Node(4)), Node(3))))      # ['balanced']
print(kinds(Node(1, Node(2, Node(3, Node(4))))))           # []  degenerate: a chain

Every shape with n nodes, generated by choosing how many nodes go left. The shape counts are the Catalan numbers, and very few shapes are complete: exactly one per n.

def shapes(n):
    """Every binary tree shape with n nodes (values are not part of the shape)."""
    if n == 0:
        return [None]
    return [Node(0, l, r) for k in range(n)
            for l in shapes(k) for r in shapes(n - 1 - k)]

for n in range(1, 8):
    all_n = shapes(n)
    tally = [sum(1 for t in all_n if test(t))
             for test in (is_full, is_complete, is_perfect, is_balanced)]
    print(n, len(all_n), tally)
# 1 1 [1, 1, 1, 1]
# 2 2 [0, 1, 0, 2]
# 3 5 [1, 1, 1, 1]
# 4 14 [0, 1, 0, 4]
# 5 42 [2, 1, 0, 6]
# 6 132 [0, 1, 0, 4]
# 7 429 [5, 1, 1, 17]

Checked against brute-force definitions on every shape up to 9 nodes (6,917 trees) and 2,000 seeded random trees of up to 60 nodes: completeness against heap numbering (the largest index must be n - 1), fullness against the leaf count, perfection against "all leaves at one depth, no single children", balance against a slow check that recomputes heights at every node, plus the implications above:

import math
import random

def nodes_with_index(root):
    out, stack = [], [(root, 0, 0)]
    while stack:
        n, i, d = stack.pop()
        if n:
            out.append((n, i, d))
            stack += [(n.left, 2 * i + 1, d + 1), (n.right, 2 * i + 2, d + 1)]
    return out

def brute(root):
    nodes = nodes_with_index(root)
    kids = [(n.left is not None) + (n.right is not None) for n, _, _ in nodes]
    leaf_depths = {d for (n, _, d), k in zip(nodes, kids) if k == 0}
    return {
        "full": kids.count(0) == kids.count(2) + 1 and 1 not in kids,
        "complete": max(i for _, i, _ in nodes) == len(nodes) - 1,
        "perfect": len(leaf_depths) == 1 and 1 not in kids,
        "balanced": all(abs(height(n.left) - height(n.right)) <= 1 for n, _, _ in nodes),
    }

def random_tree(rng, n):
    root = Node(0)
    for _ in range(n - 1):
        node = root
        while True:                                  # random walk down to an empty slot
            side = "left" if rng.random() < 0.5 else "right"
            if getattr(node, side) is None:
                setattr(node, side, Node(0))
                break
            node = getattr(node, side)
    return root

def complete_tree(n):
    nodes = [Node(0) for _ in range(n)]
    for i in range(n):
        if 2 * i + 1 < n: nodes[i].left = nodes[2 * i + 1]
        if 2 * i + 2 < n: nodes[i].right = nodes[2 * i + 2]
    return nodes[0]

rng = random.Random(31)
trees = [t for n in range(1, 10) for t in shapes(n)]
trees += [random_tree(rng, rng.randint(1, 60)) for _ in range(1_500)]
trees += [complete_tree(rng.randint(1, 60)) for _ in range(500)]
ok = True
for t in trees:
    b, n, h = brute(t), count(t), height(t)
    ok &= b == {k: k in kinds(t) for k in b}
    ok &= math.floor(math.log2(n)) <= h <= n - 1               # the height bounds
    ok &= (not b["perfect"] or b["full"] and b["complete"])     # perfect => full, complete
    ok &= (not b["complete"] or b["balanced"])                  # complete => balanced
print(len(trees), ok)                                            # 8917 True

The complexity

• Every test is O(n) time. The completeness test uses O(w) extra space for the widest level; the recursive ones use O(h) stack.
• Height is between ⌊log₂ n⌋ and n - 1, and that range is the whole story of balanced versus degenerate trees.
• Naive balance checking, recomputing heights at every node, is O(n²) on a chain, which is why the one-pass version returns heights and a failure flag together. The balanced binary tree article walks through it.

Where it goes wrong

• Mixing up full and complete. A full tree can have a long right spine with gaps on the last level; a complete tree can have a node with one child, as the lesson's tree with 6 added under 3 on the left would show.
• Checking only the root for balance. Balance is a property of every node, not just the root.
• Stopping the completeness scan at the first None. The test must keep draining the queue; a real node after a gap is exactly the failure case.
• Assuming 2^(h+1) - 1 for any tree. That is the maximum for height h, reached only by perfect trees.

When it shows up in interviews

As direct questions, "check completeness of a binary tree" and "balanced binary tree", and as the unstated assumption behind heaps (complete, stored in an array), binary search trees (fast only when balanced) and level-order traversal, which is the completeness test's engine.

How to say it in an interview

"A binary tree gives each node a left and a right slot. Full means no node has exactly one child; complete means every level is filled except the last, which fills from the left, so it maps onto an array with no gaps, which is why heaps are complete; perfect means complete and full with every leaf on one level, 2 to the h plus 1 minus 1 nodes; balanced means subtree heights differ by at most one at every node, which keeps height logarithmic. To check completeness I'd do a BFS that enqueues empty slots too and fails if a real node appears after the first empty one, O(n) time."