Core Concept Mastery • DSA Module
Binary trees come in different shapes: Full (every node has 0 or 2 children), Complete (all levels filled except last, filled left-to-right), Perfect (all internal nodes have 2 children, all leaves at same level), and Skewed (degenerates into a linked list). The shape determines performance.
Full Binary Tree: Like a decision tree where every question leads to exactly 2 answers (or stops). Complete Binary Tree: Like a company org chart where every level is fully staffed except the bottom row, filled left-to-right. Perfect Binary Tree: Like a tournament bracket where every round has exactly half the players. Skewed Tree: Like a single-file line where everyone reports to one person above them.
Shapes matter for complexity!
Every node has 0 or 2 children.
Levels filled left to right.
All internal nodes have 2 children & leaves at same level.
Every node has 0 or 2 children
Use: Expression trees
Filled left-to-right, array-storable
Use: Heaps
All leaves at same level
Use: Ideal BST
Degenerates to linked list
Worst case: O(n)
A "Complete" tree is efficiently stored in an array (Heap). For node at index i: Left child = 2i+1, Right child = 2i+2, Parent = (i-1)/2.
Height: O(log n)
Search: O(log n)
Height: O(n)
Search: O(n)
Why Shape Matters
Full Binary Tree
A binary tree where every node has either 0 or 2 children. No node has exactly 1 child.
Complete Binary Tree
A binary tree where all levels are completely filled except possibly the last level, and the last level is filled from left to right.
Perfect Binary Tree
A binary tree where all internal nodes have exactly 2 children, and all leaves are at the same level (same depth).
Skewed Binary Tree
A binary tree where every node has only one child (either all left children or all right children).
Balanced vs Unbalanced
Why This Matters
The shape of a binary tree directly affects:
Understanding tree types is crucial for analyzing complexity. A Perfect tree has O(log n) height, enabling fast operations. A Skewed tree has O(n) height, degrading to linear performance. Complete trees can be efficiently stored in arrays (heaps).
"What is the difference between a Full Binary Tree and a Complete Binary Tree?"
A Full Binary Tree requires every node to have either 0 or 2 children (no node has exactly 1 child). A Complete Binary Tree requires all levels to be filled except possibly the last level, which must be filled left-to-right. A Complete tree can be efficiently stored in an array, while a Full tree may have gaps.