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

All lessons in HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates