DS · whole subject on one page

Short notes: Data Structures

Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.

1. 📚 Arrays, Stacks, Queues & Linked Lists

Medium ●●14 PYQs →

Basic structures appear as code-tracing and "which structure is needed" questions; expression evaluation with a stack is a classic.

  • Arrays and address calculation. In a 1-D array the address of A[i] is base + (i − lower) × size. For a 2-D array stored in row-major order, A[i][j] is at base + ((i − r₀) × columns + (j − c₀)) × size; column-major swaps the roles. Access is O(1); insertion or deletion in the middle is O(n). A triangular matrix needs only n(n + 1)/2 cells.
    → address = base + (offset in elements) × size; subtract the lower bound.
  • Stack: LIFO and expression evaluation. A stack supports push, pop, peek in O(1). It converts infix to postfix (operator stack with precedence) and evaluates postfix (operand stack). It is also used for recursion, matching brackets, undo and DFS. Postfix needs no brackets and no precedence rules.
    → Postfix = operands straight out, operators wait on a stack by precedence.
  • Queues, deques and circular queues. A queue is FIFO: enqueue at the rear, dequeue at the front, both O(1). In an array of size n, a circular queue uses (rear + 1) mod n to reuse freed slots. With only front and rear pointers, full and empty look alike, so keep a count or leave one slot unused. A deque allows insertion and deletion at both ends. Two stacks can simulate a queue (amortised O(1)); two queues can simulate a stack.
    → Queue = FIFO; circular indexes use mod n; keep a count or waste a slot.
  • Linked lists. Each node holds data and a pointer. Insert or delete at a known position is O(1), but finding the position is O(n); there is no random access. Deleting a node needs its predecessor in a singly linked list, but not in a doubly linked list. Classic tasks: reverse a list (three pointers), find the middle (slow and fast pointers), detect a cycle (Floyd), merge two sorted lists.
    → Lists give O(1) insert at a known spot but O(n) access.
  • Operation cost cheat-sheet. Know the worst-case cost of search, insert and delete for each structure: unsorted array O(n)/O(1)/O(n), sorted array O(log n)/O(n)/O(n), linked list O(n)/O(1)/O(n), BST O(h), balanced BST O(log n), hash table O(1) expected, binary heap O(n) search, O(log n) insert and delete-min, O(1) find-min.
    → Know the cost table: array, list, BST, AVL, hash, heap.

Formulas

1-D address
addr(A[i]) = base + (i − lower) × size
2-D row-major
addr(A[i][j]) = base + ((i − r₀) × (#columns) + (j − c₀)) × size
2-D column-major
addr(A[i][j]) = base + ((j − c₀) × (#rows) + (i − r₀)) × size
Circular queue
next = (index + 1) mod n; count = (rear − front + n) mod n (when a slot is left empty)
Triangular matrix
n(n + 1)/2 stored elements

What GATE asks

  • ★★★Evaluate a postfix / convert infix to postfix. Run the stack by hand; track precedence and right-associative ^.
  • ★★★Stack/queue permutation or output sequence. Which output orders are possible from a given push order? Which cannot be produced?
  • ★★★Linked list code: what does it do?. Reversal, deleting nodes, finding the middle, cycle detection.
  • ★★★Implement a queue with stacks (or the reverse). Counting push/pop operations for n enqueues and dequeues.

Traps

In a stack-permutation question, the pattern 3 1 2 (a larger element out before a smaller one pushed earlier, with a smaller one still inside) is impossible.
Remember to subtract the lower bound when arrays do not start at 0.
Right-associative ^ is not popped by an equal-precedence ^.
Deleting the last node of a singly linked list is O(n) unless you keep a pointer to the previous node.

2. 🌳 Trees & Binary Search Trees

High yield ●●●15 PYQs →

Traversals, tree-shape counting, BST operations and AVL rotations are asked nearly every year.

  • Binary tree facts and formulas. A binary tree with n nodes has n − 1 edges. With n₂ nodes of degree 2 and n₀ leaves: n₀ = n₂ + 1. Height h (edges) satisfies ⌈log₂(n + 1)⌉ − 1 ≤ h ≤ n − 1. A tree of height h has at most 2^(h+1) − 1 nodes and 2ʰ leaves. The number of distinct binary trees on n nodes is the Catalan number C(2n, n)/(n + 1).
    → edges = n − 1; leaves = two-child nodes + 1.
  • Tree traversals. Preorder = root, left, right. Inorder = left, root, right. Postorder = left, right, root. Level order uses a queue. Each is O(n). Inorder of a BST is sorted. Recursive traversal uses O(h) stack space.
    → pre = N L R, in = L N R, post = L R N; BST inorder is sorted.
  • Rebuilding a tree from traversals. Preorder (or postorder) plus inorder determines the tree uniquely: the root comes from the preorder (first) or postorder (last) list; the inorder list splits into left and right parts. Preorder plus postorder does not determine a tree unless every node has 0 or 2 children. A BST is determined by its preorder alone (inorder is just the sorted keys).
    → Preorder or postorder gives the root; inorder splits sides.
  • Binary search trees. Left subtree keys < node < right subtree keys. Search, insert and delete take O(h): O(log n) for a balanced tree but O(n) in the worst case (sorted insertions). Deleting a node with two children: replace it with its inorder successor (or predecessor), then delete that node. The number of BSTs with n keys is the Catalan number.
    → BST cost = height. Delete with two children uses the inorder successor.
  • AVL trees and rotations. AVL = BST where every node has |height(left) − height(right)| ≤ 1. After an insert, rebalance the lowest unbalanced node: LL → right rotation, RR → left rotation, LR → left then right, RL → right then left. Height ≤ 1.44 log₂ n. Insertion needs at most one (single or double) rotation; deletion may need O(log n) rotations. The minimum number of nodes N(h) of an AVL tree of height h satisfies N(h) = N(h − 1) + N(h − 2) + 1.
    → LL right, RR left, LR/RL double rotations; N(h) = N(h − 1) + N(h − 2) + 1.

Formulas

Edges / leaves
edges = n − 1; n₀ = n₂ + 1; for a full k-ary tree with i internal nodes: n = k·i + 1, leaves = (k − 1)·i + 1
Height bounds (h in edges)
⌈log₂(n + 1)⌉ − 1 ≤ h ≤ n − 1; max nodes 2^(h+1) − 1
Number of binary trees / BSTs
Cₙ = C(2n, n)/(n + 1): 1, 1, 2, 5, 14, 42, 132 …
Traversals
pre: N L R; in: L N R; post: L R N; inorder(BST) = sorted
AVL minimum nodes
N(0) = 1 (or 0 for empty), N(1) = 2, N(h) = N(h − 1) + N(h − 2) + 1

What GATE asks

  • ★★★Traversal of a given tree / BST built from keys. Insert keys in order, then write postorder or inorder; or find which sequence is a valid preorder of a BST.
  • ★★★Node counting (n₀ = n₂ + 1, full k-ary tree). Leaves of a tree with given internal-node counts.
  • ★★★Height / number of nodes in a balanced or AVL tree. Maximum height of an AVL tree with n nodes, minimum nodes for a given height.
  • ★★★BST delete / insert result. Predict the shape after deletes using the inorder successor.
  • ★★★Number of BSTs / binary trees. Catalan numbers, sometimes with constraints on height.

Traps

Check whether height is counted in edges or nodes; a single node has height 0 in edges, 1 in nodes.
Preorder + postorder is ambiguous for trees with single-child nodes.
A BST requires every node in the left subtree to be smaller, not only the immediate child.
Insertion order changes the shape of a BST; sorted order gives a path.

3. ⛰️ Heaps & Priority Queues

Medium ●●9 PYQs →

Building a heap, counting swaps and recognising valid heaps are repeated question types; heaps also power heap sort and Dijkstra.

  • Heap property and array layout. A binary heap is a complete binary tree stored in an array: node i has children 2i + 1 and 2i + 2 (0-based) and parent ⌊(i − 1)/2⌋. In a max-heap every parent ≥ its children, so the maximum is at the root. There is no order between siblings. The leaves are the nodes with index ≥ ⌊n/2⌋. The height is ⌊log₂ n⌋.
    → Array heap: children 2i+1, 2i+2; the extreme is at the root; minimum of a max-heap is a leaf.
  • Building a heap: bottom-up in O(n). Heapify (sift down) every non-leaf from index ⌊n/2⌋ − 1 down to 0. Most nodes are near the bottom and move only a little, so the total work is O(n), not O(n log n). Building by repeated insertion (sift up) costs O(n log n) in the worst case, and the two methods can produce different heaps.
    → Floyd build = O(n); insertion build = O(n log n); the two can differ.
  • Priority queue operations. insert is O(log n) (add at the end, sift up). extract-max is O(log n) (move the last element to the root, sift down). find-max is O(1). Searching an arbitrary key is O(n). Finding the k largest of n numbers: a min-heap of size k gives O(n log k). Merging two heaps by rebuilding costs O(n). A d-ary heap has height log_d n.
    → Heap: insert / extract O(log n), peek O(1), search O(n).

Formulas

Indices (0-based)
left = 2i + 1; right = 2i + 2; parent = ⌊(i − 1)/2⌋. 1-based: 2i, 2i + 1, ⌊i/2⌋
Height / levels
height = ⌊log₂ n⌋; at most ⌈n / 2^(h+1)⌉ nodes of height h
Build-heap
Floyd (bottom-up): Θ(n); repeated insert: Θ(n log n)
Operations
insert O(log n); extract-max O(log n); find-max O(1); delete arbitrary known index O(log n)
Leaves
a heap of n nodes has ⌈n/2⌉ leaves

What GATE asks

  • ★★★Is this array a valid max-heap? / after insertions. Check each parent against its children, or insert keys one by one and read the array.
  • ★★★Heap after build-heap or delete-max. Simulate heapify on a small array and read a particular index.
  • ★★★Where can the minimum / maximum be?. Position of the minimum in a max-heap: among the leaves.
  • ★★★Time complexity of heap operations. Build heap O(n), k-th largest, merging heaps.

Traps

The smallest element of a max-heap is at a leaf, not necessarily the last position.
Floyd and insertion-based builds can give different arrays from the same input.
The 1-based and 0-based child formulas differ: read which one the question uses.
Searching for an arbitrary element in a heap is O(n).

4. #️⃣ Hashing

Medium ●●6 PYQs →

Insert keys into a small table by hand: a favourite 1 or 2 mark question every few years.

  • Hash functions and chaining. A hash function maps a key to a slot: h(k) = k mod m is the usual choice, with m a prime not close to a power of 2. Two keys in the same slot collide. In separate chaining each slot holds a linked list; the table never overflows. Expected cost of search is 1 + α with load factor α = n/m. Worst case (all keys collide) is O(n).
    → h(k) = k mod m; chains hold collisions; α = n/m.
  • Open addressing: linear, quadratic, double hashing. All keys live in the table itself, so n ≤ m. The i-th probe for key k: linear (h(k) + i) mod m; quadratic (h(k) + c₁i + c₂i²) mod m; double hashing (h₁(k) + i·h₂(k)) mod m. Linear probing causes primary clustering, quadratic causes milder secondary clustering. Deleting needs a tombstone marker, otherwise later searches stop too early.
    → Probe sequence rules: linear, quadratic, double; deletions need tombstones.
  • Load factor and expected cost. For chaining, unsuccessful search takes Θ(1 + α) and successful about 1 + α/2. For open addressing with uniform hashing, an unsuccessful search needs at most 1/(1 − α) probes and a successful one (1/α) ln(1/(1 − α)). Performance collapses as α → 1, so tables are resized at α around 0.5 to 0.75. Resizing by doubling gives amortised O(1) insertion.
    → Chaining 1 + α; open addressing 1/(1 − α).

Formulas

Load factor
α = n / m
Chaining
unsuccessful: Θ(1 + α); successful: ≈ 1 + α/2; worst case O(n)
Open addressing (uniform hashing)
unsuccessful ≤ 1/(1 − α); successful ≤ (1/α) ln(1/(1 − α))
Probe sequences
linear: h + i; quadratic: h + c₁i + c₂i²; double: h₁ + i·h₂ (all mod m)
Collisions
expected number of colliding pairs among n keys in m slots ≈ n(n − 1)/(2m)

What GATE asks

  • ★★★Insert keys with linear probing / chaining and read the table. Do the arithmetic carefully, slot by slot, and check which slots are empty at the end.
  • ★★★Number of collisions or longest chain. Count keys per slot, or compare strategies on the same keys.
  • ★★★Probe count for a successful / unsuccessful search. Chains: average length; open addressing: 1/(1 − α).
  • ★★★Which statement about hashing is true. Clustering, deletion, load factor above 1 for chaining, why m prime.

Traps

Chaining can have α > 1; open addressing cannot.
In open addressing a deleted slot must be marked, not emptied.
Quadratic probing may never reach some slots even when the table is not full.
Check whether the question inserts at the head or tail of a chain.