Strict/full, complete and perfect binary trees

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many edges does a tree with n nodes have? from Lesson 4.1
• Where are push and pop done in a linked stack? from Lesson 3.4.4
• What is 2⁰ + 2¹ + … + 2ʰ? from Lesson 0.2.1

1 · The Hook

🎣

A knockout cricket tournament pairs teams in each round: two winners meet in the next match. Drawn as a tree, every match has at most two inputs. Restricting nodes to at most two children keeps trees simple to store and to walk, and leads to precise counting rules that GATE loves.

2 · Predict First

🤔

A binary tree has every level completely filled down to depth 3. How many nodes does it have? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

15 = 1 + 2 + 4 + 8 = 2⁴ − 1. Such a tree is called perfect.

Binary trees

A binary tree is either empty or a node with a left subtree and a right subtree, each itself a binary tree. Left and right are different positions: a node with only a left child is a different binary tree from one with only a right child.

Strict (full) binary tree

Every node has 0 or 2 children — never exactly one. Many books call this a full binary tree; some use “full” to mean perfect (below). GATE questions usually define the term; if not, “full” most often means 0 or 2 children.

Complete binary tree

Every level is completely filled except possibly the last, and the last level’s nodes are as far left as possible (no gaps). This is exactly the shape that fits an array without holes (Lesson 4.2.3) and the shape of heaps (Phase 5).

Perfect binary tree

All internal nodes have 2 children and all leaves are at the same depth: every level is full. A perfect tree is both strict and complete.

Skewed tree

Every node has only one child (all left, all right, or mixed): the tree is a path, with height n − 1. It behaves like a linked list.

4 · Visual

Perfect (also strict and complete).

Complete, not strict (3 has one child).

Strict, not complete (gap under 2).

Skewed: height n − 1.

complete?  fill level by level, left to right, no gaps:

       1                 1                  1
     /   \             /   \              /   \
    2     3           2     3            2     3
   / \   /           / \     \          / \
  4   5 6           4   5     7        4   5
  complete        NOT complete:       complete
                  gap before 7        (last level left-packed)

Complete = no holes when the levels are read left to right.

5 · Worked Examples

Example 1 Easy

Classify each tree in the Visual section as strict, complete, perfect or skewed.

Solution

Top left: perfect, strict, complete. Top right: complete only. Bottom left: strict only. Bottom right: skewed (neither strict nor complete beyond the root).

Example 2 Medium

Is every complete binary tree strict? Is every perfect binary tree complete?

Solution

No: a complete tree may have one node with a single left child on the last level (e.g. 6 nodes). Yes: a perfect tree fills every level, which is complete.

Example 3 GATE

A complete binary tree has 10 nodes. How many nodes are on its last level, and how many nodes have exactly one child?

Solution

Levels 0–2 are full: 1 + 2 + 4 = 7 nodes; the last level holds 10 − 7 = 3. The 3 last-level nodes are the children of the first two level-2 nodes: the first has 2 children, the second has 1. So 1 node has exactly one child.

6 · GATE Traps

⚠️

• “Full binary tree” has two meanings in textbooks (0-or-2 children, or perfect); check the definition given.
• Complete means filled level by level from the left, not merely “all levels full”.
• A complete tree can have at most one node with exactly one child, and that child is a left child.
• Left and right children are distinct positions.
• A skewed tree of n nodes has height n − 1.

8 · Memory Hook

🧠

“Strict: twins or no kids. Complete: no holes reading left to right. Perfect: a full pyramid.”

9 · Connect the Dots

Lesson 4.1 named the parts of a tree; this lesson named shapes of binary trees. Shapes come with exact counts: how many nodes fit in a given height, and how leaves relate to nodes with two children. Next lesson answers: what are those counting rules, and how tall must a binary tree with n nodes be?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markShapes

A binary tree in which every node has 0 or 2 children is:

• (A) perfect
• (B) strict (full)
• (C) skewed
• (D) complete

Q2MCQ1 markComplete

Which statement about complete binary trees is true?

• (A) The height is always n − 1.
• (B) All levels except possibly the last are full, and the last is filled from the left.
• (C) All leaves are at the same depth.
• (D) Every node has 0 or 2 children.

Q3NAT1 markPerfect

How many nodes does a perfect binary tree of height 4 (edges) have?

Numerical answer: ________

Q4NAT2 marksComplete

A complete binary tree has 20 nodes. How many nodes are on its last level?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true?

• (A) A skewed tree with n nodes has height n − 1.
• (B) A complete binary tree has at most one node with exactly one child.
• (C) Every complete binary tree is perfect.
• (D) Every perfect binary tree is strict.

11 · Rule Card

• Binary tree: each node has a left and a right subtree (possibly empty); left ≠ right.
• Strict/full: every node 0 or 2 children (some books: full = perfect).
• Complete: all levels full except the last, which is left-packed.
• Perfect: all levels full (strict + complete).
• Skewed: one child per node; height n − 1.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

binary treeleft / right subtreestrict (full) binary treecomplete binary treeperfect binary treeskewed tree

13 · Answer Vault