Courses / HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates
3.3 Trees and Heaps
Area 3 – Data Structures & Algorithms (10%) · 45 min read · 23 MCQs to check yourself
Tree vocabulary
Root (top), parent, child, leaf (no children), height (longest root-to-leaf path), depth, subtree. A tree with n nodes has n − 1 edges.
Binary trees
Each node has at most 2 children. A full binary tree of height h has at most 2^(h+1) − 1 nodes (counting the root at height 0). Traversals (remember where the root goes):
| Traversal | Order |
|---|---|
| Pre-order | Root → Left → Right |
| In-order | Left → Root → Right |
| Post-order | Left → Right → Root |
| Level-order | Level by level (uses a queue = BFS) |
Binary Search Tree (BST)
Left subtree < node < right subtree. In-order traversal of a BST gives sorted order. Search/insert/delete: O(log n) if balanced, O(n) if it becomes a chain (insert sorted data). AVL and Red-Black trees stay balanced by rotations. B-trees / B+ trees are used for database indexes.
Heaps
A complete binary tree stored in an array. Max-heap: parent ≥ children (largest at root); min-heap: parent ≤ children. For index i (0-based): children 2i + 1 and 2i + 2, parent ⌊(i − 1)/2⌋. Insert / delete-root O(log n); build-heap O(n); heap sort O(n log n). Trie – tree for strings (autocomplete); segment tree – range queries.
Binary search tree – insertion and traversal (Gate Smashers)
This lesson ends with a quiz of 23 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: 3.2 Linear Data Structures – Arrays, Linked Lists, Stacks, Queues · Next: 3.4 Graphs