.png)
DSA Series Chapter 12 - BINARY TREE BASICS, TERMINOLOGY & TYPES OF BINARY TREES
Objective of Phase 1
Phase 1 builds strong conceptual foundations for Binary Trees. This phase is theory-heavy and is crucial for:
Understanding later coding phases
University examinations
GATE and interview conceptual questions
No advanced coding is expected here; the focus is on definitions, properties, and clarity of terms.
1. What is a Binary Tree?
A Binary Tree is a non-linear data structure in which:
Each node can have at most two children
These children are referred to as the left child and right child
Formal Definition (Exam-ready)
A binary tree is a hierarchical data structure in which each node has at most two children, called the left child and the right child.
2. Why Binary Trees Are Needed
Binary trees are used when:
Data has a hierarchical relationship
Fast searching, insertion, or deletion is required (structure-dependent)
Real-World Applications
File system hierarchy
Expression evaluation
Compiler syntax trees
Artificial intelligence decision trees
3. Binary Tree vs Linear Data Structures
| Aspect | Linear DS (Array/LL) | Binary Tree |
|---|---|---|
| Data arrangement | Sequential | Hierarchical |
| Traversal | Single direction | Multiple traversal paths |
| Relationship | One-to-one | One-to-many |
| Examples | Array, Stack | Binary Tree |
4. Binary Tree vs Binary Search Tree (Conceptual Only)
| Binary Tree | Binary Search Tree |
|---|---|
| No ordering rule | Follows ordering property |
| Traversal output unsorted | Inorder gives sorted output |
| Used for structure | Used for searching |
Important note: All BSTs are Binary Trees, but not all Binary Trees are BSTs.
5. Basic Terminology of Binary Tree
5.1 Node
Basic unit of a tree
Contains data and links to children
5.2 Root Node
Topmost node of the tree
Has no parent
5.3 Parent Node
A node that has one or more children
5.4 Child Node
Node directly connected below a parent
5.5 Sibling Nodes
Nodes having the same parent
6. Leaf and Internal Nodes
Leaf Node (External Node)
Node with no children
Internal Node
Node with at least one child
7. Degree of a Node
Number of children a node has
| Node Type | Degree |
|---|---|
| Leaf Node | 0 |
| Node with one child | 1 |
| Node with two children | 2 |
Degree of a Binary Tree
Maximum degree of any node in the tree
For Binary Tree, degree ≤ 2
8. Level of a Node
Level indicates the position of a node in the tree
Root node is at Level 0 (sometimes Level 1 in some textbooks)
9. Depth of a Node
Number of edges from the root to that node
Depth(root) = 0
10. Height of a Binary Tree
Definition
Number of nodes on the longest path from root to a leaf
Important Notes
Height of single-node tree = 1
Height of empty tree = 0
11. Height vs Depth (Very Important)
| Aspect | Height | Depth |
|---|---|---|
| Measured from | Node to leaf | Root to node |
| Applied to | Tree or node | Node |
| Direction | Downwards | Downwards |
12. Properties of Binary Tree
Property 1: Maximum Nodes at Level L
Maximum nodes = 2^L
Example:
Level 0 → 1 node
Level 1 → 2 nodes
Level 2 → 4 nodes
Property 2: Maximum Nodes in a Binary Tree of Height h
Maximum nodes = 2^h − 1
Property 3: Minimum Height for n Nodes
Minimum height = ⌈log2(n + 1)⌉
13. Empty Binary Tree
A tree with no nodes
Height = 0
Root = NULL
14. Common Exam Mistakes
Confusing height with depth
Assuming ordering in Binary Tree
Using BST properties in Binary Tree
Wrong root level assumption
TYPES OF BINARY TREES
Objective of Phase 2
Phase 2 focuses on structural understanding of Binary Trees. Knowing types is essential for:
Solving traversal and insertion/deletion problems
Dry-run exercises in exams
Recognizing tree patterns in interviews
This phase is conceptual + diagrammatic, preparing the student for coding phases.
1. Full Binary Tree
Definition
A binary tree in which every node other than the leaves has exactly two children.
Properties
Every internal node has degree 2
Leaf nodes may exist at different levels
Maximum nodes at height h = 2^h - 1
Diagram
1
/ \
2 3
/ \ / \
4 5 6 7
Notes
Also called Proper Binary Tree or Strict Binary Tree
Used in complete expression trees
2. Complete Binary Tree
Definition
A binary tree in which all levels are completely filled except possibly the last level, and the last level has all nodes as left as possible.
Properties
Last level nodes are filled from left to right
Height = ⌊log2(n)⌋
Diagram
1
/ \
2 3
/ \ /
4 5 6
Notes
Used in heap implementation
Maintains minimal height for given nodes
3. Perfect Binary Tree
Definition
A binary tree in which all internal nodes have two children and all leaves are at the same level.
Properties
Nodes = 2^h - 1 (where h = height)
Height = log2(n + 1)
Diagram
1
/ \
2 3
/ \ / \
4 5 6 7
Notes
Special case of full binary tree
Ideal for balanced structures
4. Degenerate (Skewed) Binary Tree
Definition
A binary tree in which each parent node has only one child.
Types
Left Skewed (all nodes have only left child)
Right Skewed (all nodes have only right child)
Diagram
Right Skewed:
1
\
2
\
3
\
4
Left Skewed:
1
/
2
/
3
/
4
Notes
Resembles linked list structure
Height = number of nodes (worst-case for tree operations)
5. Comparison Table of Binary Tree Types
| Type | All Internal Nodes Have Two Children? | Leaves at Same Level? | Example Use |
|---|---|---|---|
| Full Binary Tree | Yes | No necessarily | Expression Tree |
| Complete Binary Tree | Not necessarily | No | Heap |
| Perfect Binary Tree | Yes | Yes | Balanced Tree Structure |
| Degenerate/Skewed Tree | No | No | Linked List scenario |
6. Identification Tips for Exams
Perfect vs Full: Perfect = all leaves same level, Full = internal nodes have 2 children
Complete vs Full: Complete = last level can be partially filled, Full = all internal nodes 2 children
Degenerate: Height = number of nodes, resembles a linked list
Draw diagrams to verify quickly
7. Common Exam Mistakes
Confusing Full and Perfect trees
Miscounting nodes at last level for Complete tree
Assuming skewed trees are balanced
ALSO CHECK
ALSO CHECK
Comments
Post a Comment