Data Structures
Trees, stacks, queues, and graphs.
6 questions
JuniorTheoryVery commonHow do a stack and a queue differ?
How do a stack and a queue differ?
A stack is LIFO — last in, first out — pushing and popping at one end, like a stack of plates. A queue is FIFO — first in, first out — adding at the back and removing from the front. Both do O(1) insert and remove.
Common mistakes
- ✗Swapping the definitions, calling a stack
FIFOand a queueLIFO - ✗Thinking a queue removes from the back instead of the front
- ✗Believing the two structures return items in the same order
Follow-up questions
- →How would you implement a queue using two stacks?
- →What real problems map naturally onto a
LIFOstack?
JuniorTheoryCommonWhat is a graph?
What is a graph?
A graph models connections: nodes (vertices) joined by edges, where directly linked nodes are neighbors. It can be directed or undirected and weighted or unweighted; a directed edge A→B makes B a neighbor of A only.
Common mistakes
- ✗Assuming every graph is connected and acyclic, conflating it with a tree
- ✗Forgetting that edges can be directed, so neighborship may be one-way
- ✗Overlooking that edges can carry weights for cost or distance
Follow-up questions
- →What is the difference between a directed and an undirected graph?
- →How do you detect a cycle in a directed graph?
JuniorTheoryCommonWhat is a tree?
What is a tree?
A tree is a connected acyclic graph: n nodes joined by exactly n-1 edges, with a unique path between any two nodes. It typically has one root, with parent→child relationships flowing down and no cycles.
Common mistakes
- ✗Allowing cycles, which turns the structure into a general graph
- ✗Forgetting a tree with
nnodes has exactlyn-1edges - ✗Assuming a tree can be disconnected into independent components
Follow-up questions
- →Why does a tree with
nnodes always haven-1edges? - →What distinguishes a binary tree from a general tree?
MiddleTheoryCommonWhat is a binary search tree?
What is a binary search tree?
A binary tree where each node has ≤2 children and the BST invariant holds: every key in the left subtree is smaller, every key in the right larger. This gives O(log n) search and insert when balanced, degrading to O(n) if skewed.
Common mistakes
- ✗Ignoring the ordering invariant and allowing arbitrary child keys
- ✗Assuming lookups are always
O(log n)regardless of tree shape - ✗Letting a node have more than two children in a
BST
Follow-up questions
- →How does a self-balancing tree keep
O(log n)guarantees? - →What input order turns a
BSTinto anO(n)chain?
MiddleTheoryOccasionalHow can a graph be represented in memory?
How can a graph be represented in memory?
Two common ways: an adjacency list, where each node stores its neighbors — O(V+E) space, great for sparse graphs; or an adjacency matrix, a V×V grid of edge presence — O(V^2) space but O(1) edge lookup, suited to dense graphs.
Common mistakes
- ✗Confusing the space costs: list is
O(V+E), matrix isO(V^2) - ✗Thinking an adjacency list gives
O(1)edge-existence checks - ✗Picking a matrix for a sparse graph and wasting memory
Follow-up questions
- →When is an adjacency matrix the better choice over a list?
- →How does representation affect
BFSandDFSruntime?
MiddleTheoryOccasionalWhat is a heap, and what is it used for?
What is a heap, and what is it used for?
A heap is a complete binary tree with the heap property — in a min-heap every parent ≤ its children, so the minimum sits at the root. It backs a priority queue with O(log n) insert and extract-min and O(1) peek; used in Dijkstra.
Common mistakes
- ✗Believing a heap stores elements fully sorted like an array
- ✗Claiming extract-min is
O(1)instead ofO(log n)after sift-down - ✗Confusing a heap with a
BSTand its left<root<right rule
Follow-up questions
- →How is a binary heap stored compactly inside a flat array?
- →Why does building a heap from
nitems takeO(n), notO(n log n)?
