Quiz · Medium
Twenty questions on traversals, BSTs, heaps, hash tables, stacks, queues and graph basics, with diagrams to read.
The diagram shows a binary tree with dotted marks on the left of each node. Which traversal does it illustrate? Root F, children B and G.

In-order
Post-order
Pre-order
Level-order
Marking each node on its left means it is visited before its children, which is pre-order (F, B, A, D, C, E, G, I, H). In-order would mark the bottom of each node; post-order the right side.
What is the post-order traversal of the tree in the picture?

A, C, E, D, B, H, I, G, F
F, B, A, D, C, E, G, I, H
A, B, C, D, E, F, G, H, I
F, B, G, A, D, I, C, E, H
Post-order visits left subtree, right subtree, then the node. Left of F: A, C, E, D, B. Right of F: H, I, G. Then F. F, B, A, D, C, E, G, I, H is the pre-order and A, B, C, D, E, F, G, H, I is the in-order.
Inserting the keys 1, 2, 3, 4, 5 in that order into an empty plain (unbalanced) BST produces a tree of what height?
2
3
1
4
Each key is larger than all before it, so each becomes the right child of the previous one. The tree is a chain of 5 nodes with height 4 (edges). That is why self-balancing trees exist.
Which traversal of a BST visits the keys in ascending order?
Pre-order
In-order
Level-order
Post-order
In-order visits left subtree, node, right subtree, and in a BST everything on the left is smaller. Pre-order and post-order give the root first or last, so they are not sorted.
Which diagram shows a stack?




The stack diagram shows push and pop at the same end (LIFO). The queue adds at the back and removes from the front.
In the array representation of a 0-indexed binary heap, where is the parent of the element at index 7?
Index 4
Index 2
Index 3
Index 6
Parent = floor((i − 1) / 2) = floor(6 / 2) = 3. Index 4 would be the parent if you wrongly used i / 2 rounded up.
A min-heap currently holds [2, 4, 3, 9, 5]. After inserting 1, what is the array?
[1, 4, 2, 9, 5, 3]
[1, 2, 3, 9, 5, 4]
[2, 4, 3, 9, 5, 1]
[1, 2, 4, 3, 9, 5]
Append 1 at index 5 (parent index 2 holds 3): swap → [2, 4, 1, 9, 5, 3]. Parent of index 2 is index 0 (value 2): swap → [1, 4, 2, 9, 5, 3]. Root is now the minimum.
What is the average-case time to look up a key in a hash table with a good hash function and a bounded load factor?
O(log n)
O(n)
O(n log n)
O(1)
With uniform hashing each bucket holds about α entries, a constant when the table resizes to keep α bounded. O(n) is the worst case when everything collides.
The diagram shows John Smith and Sandra Dee stored in the same bucket as a linked list. What is this collision-handling method called?

Linear probing
Separate chaining
Double hashing
Cuckoo hashing
Separate chaining keeps a list per bucket. Probing methods store entries in the table itself. Image: Jorge Stolfi, CC BY-SA 3.0, via Wikimedia Commons.
Which statement about a dynamic array's append is correct?
Every append is O(1) in the worst case
Append is O(n) on average because of copying
Append is O(1) amortized, O(n) on a resize
Append is O(log n) amortized
Resizing copies n elements but happens only after about n cheap appends, so the average is constant. A single append can still be O(n).
You need a structure that returns the smallest element in O(1) and supports insert in O(log n). Which fits best?
Min-heap
Sorted linked list
Hash table
Stack
A min-heap keeps the minimum at the root (peek O(1)) and inserts via sift-up in O(log n). A sorted linked list inserts in O(n).
What does the Left Right case of an AVL tree need?

One right rotation
One left rotation
Recolouring only
A left rotation on the left child, then a right rotation on the root
The imbalance is a 'zig-zag' on the left side, so a single rotation would not fix it. First rotate the left child left, which turns it into a Left Left case, then rotate right. Recolouring belongs to red-black trees. Image: CyHawk, CC BY-SA 3.0, via Wikimedia Commons.
Which red-black tree property is violated by a red node having a red child?

The root must be black
A red node cannot have a red child
Every path has the same number of black nodes
NIL leaves must be black
Rule 4 forbids red-red parent-child pairs. Fixing it uses recolouring or rotations after insertion. Image: Cburnett, CC BY-SA 3.0, via Wikimedia Commons.
Which Python collection gives O(1) removal from the left end?
list
tuple
collections.deque
set
deque is a doubly ended queue with O(1) appendleft and popleft. list.pop(0) shifts all remaining elements and is O(n).
Which representation of a graph with 1,000 vertices and 2,000 edges uses the least memory?
Adjacency list
Adjacency matrix
They use the same
Edge matrix of size E × E
The list needs O(V + E) = about 3,000 entries (times two for undirected), the matrix needs V² = 1,000,000 cells. The graph is sparse.
A graph search visits vertices level by level and finds the fewest-edge path in an unweighted graph. Which search is it?

Depth-first search
Binary search
Topological sort
Breadth-first search
BFS uses a queue and explores in rings of increasing distance. DFS dives deep and does not guarantee shortest paths. Image of BFS order: Alexander Drichel, CC BY 3.0, via Wikimedia Commons.
A hash table has m = 8 buckets and stores n = 6 entries. What is the load factor?
1.33
0.75
6
0.125
α = n / m = 6 / 8 = 0.75. The value 1.33 is the inverse (m / n).
True or false: an in-order traversal of a binary heap returns its elements in sorted order.
True
False
A heap only guarantees parent ≥ child (max-heap). Siblings and cousins are unordered, so in-order output is generally not sorted. To get sorted output you repeatedly extract the root.
Which data structure is the best fit for implementing an undo feature?
Queue
Hash set
Stack
Min-heap
The most recent action must be undone first: last in, first out.
True or false: deleting a node with two children from a BST can be done by replacing its key with its in-order successor and deleting that successor.
True
False
The successor (smallest key in the right subtree) is larger than everything on the left and smaller than the rest of the right subtree, so BST order is preserved. It has at most one child, which makes its removal easy.