Data Structures and Algorithms
Core concepts
You must know the behaviour and complexity of arrays, linked lists, stacks, queues, trees (binary search trees, AVL, heaps), hash tables, and graphs. Be able to state average and worst-case time for search, insertion, and deletion, and to explain why a balanced tree gives O(log n) while a degenerate BST degrades to O(n). Understand traversal orders (preorder, inorder, postorder, level order), hashing and collision resolution (chaining, open addressing), and graph representations (adjacency matrix versus list). For algorithms, know sorting (bubble, insertion, merge, quick, heap), searching (linear, binary), and the greedy versus dynamic programming distinction, plus Big-O, Big-Theta, and Big-Omega notation.
Traps
Examiners like asking which sort is stable, which has O(n log n) worst case, and which is fastest on nearly sorted data. Remember merge sort guarantees O(n log n) but needs O(n) extra space; quicksort is O(n log n) average but O(n^2) worst case; heapsort is in-place but not stable. Binary search requires a sorted array and gives O(log n). A stack is LIFO, a queue FIFO - do not swap them. Also watch for confusion between the height of a tree and the number of nodes.
Worked example
Insert 50, 30, 70, 20, 40, 60, 80 into a BST. The root is 50; 30 and 70 become its children; 20 and 40 attach to 30; 60 and 80 attach to 70. An inorder traversal yields 20, 30, 40, 50, 60, 70, 80 - sorted ascending. Rule of thumb: inorder traversal of any BST is always sorted, which is a fast way to verify an answer.