Complete vs full vs perfect binary trees in Data Structures Theory - Visual Side-by-Side Comparison

Concept Flow - Complete vs full vs perfect binary trees

Start with Binary Tree

↓

Are all levels except the last fully filled?

↓

Is last level filled left to right?

↓

Complete Tree

↓

All nodes have 0 or 2 children?

↓

Full Tree

This flow shows how to classify a binary tree by checking if all levels except the last are fully filled, if the last level is filled left to right, and if all nodes have 0 or 2 children.

Execution Sample

Data Structures Theory

Tree:
      1
     / \
    2   3
   / 
  4  

This tree is complete but not full or perfect because last level is not fully filled and node 2 has only one child.

Analysis Table

Step	Check	Condition	Result	Classification
1	Check if all levels except last are fully filled	Levels 0 and 1 fully filled	True	Continue
2	Check if last level is filled left to right	Node 4 is left child, no gaps	True	Continue
3	Check if all nodes have 0 or 2 children	Node 2 has only one child	False	Not Full
4	Check if all levels fully filled	Last level not fully filled	False	Not Perfect
5	Conclusion	-	-	Tree is Complete but not Full or Perfect

💡 Last level is filled left to right but not fully filled, and node 2 has only one child, so tree is Complete only.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
All levels except last fully filled	Unknown	True	True	True	True
Last level filled left to right	Unknown	Unknown	True	True	True
All nodes have 0 or 2 children	Unknown	Unknown	Unknown	False	False
Tree classification	Unknown	Unknown	Unknown	Not Full	Complete only

Key Insights - 3 Insights

Why is the tree not considered full even though most nodes have two children?

Because node 2 has only one child, violating the full tree rule that every node must have 0 or 2 children (see execution_table step 3).

Why is the tree classified as complete if the last level is not fully filled?

Because the last level is filled from left to right without gaps, which satisfies the complete tree condition (see execution_table step 2).

What makes a tree perfect compared to complete?

A perfect tree has all levels fully filled with no missing nodes, unlike a complete tree which allows the last level to be partially filled left to right (see execution_table steps 1 and 4).

Visual Quiz - 3 Questions

Look at the execution table, at which step do we find the tree is not full?

A Step 4

B Step 3

C Step 2

D Step 1

💡 Hint

Check the 'All nodes have 0 or 2 children' condition in execution_table step 3.

According to variable_tracker, what is the final classification of the tree?

A Complete only

B Full and Perfect

C Perfect only

D Not Complete

💡 Hint

Look at the 'Tree classification' row in variable_tracker final column.

If node 2 had two children, how would the classification change?

A Tree remains Complete only

B Tree becomes Perfect

C Tree becomes Full and Complete

D Tree becomes Not Complete

💡 Hint

Refer to key_moments about full tree condition and execution_table step 3.

Concept Snapshot

Complete Binary Tree:
- All levels fully filled except possibly last
- Last level filled left to right

Full Binary Tree:
- Every node has 0 or 2 children

Perfect Binary Tree:
- All levels fully filled
- Tree is both full and complete

Full Transcript

This visual execution trace compares complete, full, and perfect binary trees. It starts by checking if all levels except the last are fully filled, then if the last level is filled left to right, and finally if every node has either zero or two children. The example tree is complete because its last level is filled left to right without gaps, but not full because one node has only one child. It is also not perfect because the last level is not fully filled. Key moments clarify why the tree is not full and how perfect trees differ from complete ones. The quizzes test understanding of these conditions and classifications.