Complete vs Full vs Perfect Binary Trees

Types of Binary Trees

Binary trees have several structural classifications that describe how nodes are arranged. Understanding these distinctions is important for array-based representations, heap implementations, and interview questions.

Full Binary Tree

Every node has either 0 or 2 children — no node has exactly one child.

Full:           Not Full:
    1               1
   / \             / \
  2   3           2   3
 / \             /
4   5           4

Properties:

• Number of leaf nodes = number of internal nodes + 1
• Total nodes is always odd

Complete Binary Tree

Every level is completely filled except possibly the last level, which is filled from left to right.

Complete:       Not Complete:
    1               1
   / \             / \
  2   3           2   3
 / \             / \   \
4   5           4   5   7

Properties:

• Height = floor(log2(n))
• Can be efficiently stored in an array: for node at index i, left child is at 2i+1, right child at 2i+2
• Binary heaps are always complete binary trees

Perfect Binary Tree

Every level is completely filled — it is both full and complete. All leaf nodes are at the same level.

Perfect (height 3):
        1
       / \
      2   3
     / \ / \
    4  5 6  7

Properties:

• Total nodes = 2^h - 1 (where h is height counting nodes)
• Leaf nodes = 2^(h-1)
• All leaves at the same depth
• Rarest form — only exists for specific node counts (1, 3, 7, 15, 31, ...)

Degenerate (Pathological) Tree

Every internal node has exactly one child — effectively a linked list.

1
 \
  2
   \
    3
     \
      4

Height equals node count, and all tree operations degrade to O(n).