📘 Introduction & Quick Revision Notes: Trees (DSSSB TGT/PGT CS)
Trees are non-linear, hierarchical data structures that account for 6 to 10 questions in every DSSSB TGT Computer Science (Post Codes 91/20, 39/22, etc.) and PGT Computer Science (Post Codes 70/20, 29/22, etc.) examination. Below are high-yield formulas and rules compiled from 2014–2025 papers.
1. Essential Binary Tree Formulas (Frequently Tested)
- Maximum nodes at level i (root at level 0): 2i (If root is at level 1: 2i−1)
- Maximum nodes in a Binary Tree of height h (root at height 0): 2h+1 − 1
- Minimum nodes in a Binary Tree of height h: h + 1
- Minimum height of a Binary Tree with n nodes: ⌊log2 n⌋
- Leaf vs. Internal Nodes (Strict/Full Binary Tree): If there are n internal nodes of degree 2, total leaf nodes L = n + 1. Total nodes N = 2n + 1.
- Number of unlabeled Binary Trees with n nodes (Catalan Number): Cn = (2n)! / [(n + 1)! × n!]
- Number of labeled Binary Trees with n nodes: Cn × n!
- Null pointers in a Binary Tree of n nodes: Always n + 1 (Used in Threaded Binary Trees).
2. Tree Traversals & Reconstruction
- Inorder (L-Root-R): Produces sorted ascending output in a Binary Search Tree (BST).
- Preorder (Root-L-R): First element is always the Root; generates Prefix notation in Expression Trees.
- Postorder (L-R-Root): Last element is always the Root; used for deleting/freeing a tree and Postfix notation.
- Unique Tree Construction: Requires Inorder + Preorder OR Inorder + Postorder. (Preorder + Postorder alone cannot construct a unique general binary tree unless it is a Full Binary Tree).
3. Comparison of Search & Balanced Trees
| Tree Type | Key Property | Search / Insert / Delete (Worst) | Primary Application |
|---|---|---|---|
| BST | Left < Root < Right | O(n) (Skewed), O(log n) Avg | Dynamic searching & sorting |
| AVL Tree | Balance Factor ∈ {−1, 0, +1} | O(log n) | Fast lookups (strictly balanced) |
| Red-Black Tree | Root & Leaves Black; No 2 adjacent Reds | O(log n) | Java TreeMap, C++ STL map/set |
| B-Tree / B+ Tree | Multi-way balanced; B+ stores data only at leaves | O(logm n) | Database indexing & File systems |
| Binary Heap | Complete Binary Tree; Max/Min at root | Find Max/Min: O(1), Insert/Del: O(log n) | Priority Queue, Heap Sort |
.png)