DSSSB TGT PGT Computer Science PYQ: 160+ Tree Data Structure MCQs with Notes & Interactive Quiz (2014–2025)

📘 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
📊 Live Score: 0 / 0 Attempted
💚

Enjoyed this post?

Help us create more content by sharing it with a friend!

Share on WhatsApp

Post a Comment

Please do note create link post in comment section

Previous Post Next Post