The 4 Data Structures That Will Make You Stand Out in Senior Interviews
In the first part we covered the 5 fundamental structures that appear in 70% of interviews. Now let’s go up a level.
If you’re applying for senior roles at companies like MercadoLibre, Nubank, Cornershop, or looking for remote positions at Silicon Valley startups, these four structures are what separate good candidates from excellent ones.
1. Tree — The Foundation of Hierarchy
A tree is a hierarchical structure where data is organized in nodes connected by parent-child relationships. Unlike linear structures (arrays, lists), trees allow you to naturally represent hierarchical relationships.
Anatomy of a tree
- Root: The top node, entry point to the tree
- Parent/Child: A node that connects downward has children; upward, a parent
- Leaf: A node with no children
- Height: Maximum distance from the root to any leaf
Structure of a node
class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.data = value;
this.left = null;
this.right = null;
}
}
Fundamental traversals
The four traversals you must master:
| Traversal | Order | Typical use |
|---|---|---|
| Inorder | Left → Root → Right | Get ordered elements (in BST) |
| Preorder | Root → Left → Right | Copy/serialize the tree |
| Postorder | Left → Right → Root | Delete tree, evaluate expressions |
| Level Order | Level by level | BFS, find minimum depth |
When to use it
- Represent hierarchies (org charts, file systems, DOM)
- Foundation for more specific structures (BST, Heaps, Tries)
- Recursion and divide-and-conquer problems
Typical interview question
“Find the maximum height of a binary tree.”
Strategy: Recursion. Height is 1 + max(left_height, right_height). Base case: null node returns 0.
2. Binary Search Tree (BST) — Ordered Search
A BST is a binary tree with a special property: for each node, all values to the left are smaller and all values to the right are larger.
This property enables searches in O(log n) — similar to binary search, but in a tree structure.
The BST property
15
/ \
8 23
/ \ / \
4 11 17 27
For node 15: everything to the left (8, 4, 11) is smaller; everything to the right (23, 17, 27) is larger.
Key operations
// Search in BST
TreeNode search(TreeNode root, int target) {
if (root == null || root.data == target)
return root;
if (target < root.data)
return search(root.left, target);
else
return search(root.right, target);
}
Complexity
| Operation | Average | Worst case (unbalanced) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Deletion | O(log n) | O(n) |
| Inorder | O(n) | O(n) |
Important: An unbalanced BST degenerates into a linked list. That’s why self-balancing trees exist (AVL, Red-Black).
When to use it
- You need ordered data with frequent insertion/deletion
- Implement ordered sets and maps
- Problems requiring finding successor/predecessor
Typical interview question
“Validate if a binary tree is a valid BST.”
Strategy: Inorder traversal should produce a strictly increasing sequence. Or use ranges: each node must be between a valid minimum and maximum.
3. Heap — Priority Queues and Top-K
A Heap is a complete binary tree that maintains the heap property: each parent is greater (max-heap) or smaller (min-heap) than its children.
The magic of the heap: access the maximum or minimum element in O(1), and insert/delete in O(log n).
Min-Heap vs Max-Heap
- Min-Heap: The parent is always less than or equal to its children. The root is the minimum.
- Max-Heap: The parent is always greater than or equal to its children. The root is the maximum.
Implementation with array
Heaps are efficiently implemented with arrays (without pointers):
For index i:
- Left child: 2*i + 1
- Right child: 2*i + 2
- Parent: (i - 1) / 2
// In Java, use PriorityQueue
PriorityQueue<Integer>
``````java
minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap.offer(5); // insert
int min = minHeap.peek(); // view minimum (O(1))
int removed = minHeap.poll(); // extract minimum (O(log n))
Complexity
| Operation | Time |
|---|---|
| Peek (view root) | O(1) |
| Insert | O(log n) |
| Extract (remove root) | O(log n) |
| Heapify (build heap) | O(n) |
When to Use It
- Implement priority queues
- “Top K” or “K-th largest/smallest” problems
- Graph algorithms (Dijkstra, Prim)
- Merge K sorted lists
Typical Interview Question
“Find the K most frequent elements in an array.”
Strategy: HashMap to count frequencies + Min-Heap of size K. Or use a Max-Heap and extract K times.
4. Graph — Modeling Complex Relationships
A graph represents relationships between entities using vertices (nodes) and edges (connections). It’s the most flexible and powerful structure for modeling the real world.
Types of Graphs
| Type | Description | Example |
|---|---|---|
| Directed | Edges have direction (A→B) | Twitter follows, dependencies |
| Undirected | Bidirectional edges (A—B) | Facebook friends, routes |
| Weighted | Edges have weight/cost | Maps with distances |
| DAG | Directed acyclic graph | Build systems, scheduling |
Representations
1. Adjacency Matrix — O(1) to check edges, O(V²) space
int[][] graph = new int[V][V];
graph[u][v] = 1; // edge from u to v
2. Adjacency List — Space efficient O(V+E), ideal for sparse graphs
Map<Integer, List<Integer>> graph = new HashMap<>();
void addEdge(int u, int v) {
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // if undirected
}
Essential Algorithms
| Algorithm | Purpose | Complexity |
|---|---|---|
| BFS | Shortest path (unweighted), level by level | O(V + E) |
| DFS | Explore all paths, detect cycles | O(V + E) |
| Dijkstra | Shortest path (positive weights) | O((V+E) log V) |
| Topological Sort | Sort DAG by dependencies | O(V + E) |
When to Use It
- Social networks, recommendation systems
- Routes and navigation (Google Maps)
- Task dependencies, builds, courses
- Cycle detection, connected components
Typical Interview Question
“Given a graph, determine if a path exists between two nodes.”
Strategy: BFS or DFS from the source node. If you reach the destination, a path exists.
Quick Comparison
| Structure | Strength | Typical Complexity |
|---|---|---|
| Tree | Hierarchies, recursion | O(n) traversal |
| BST | Ordered search | O(log n) average |
| Heap | Access to min/max | O(1) peek, O(log n) insert |
| Graph | Complex relationships | O(V + E) traversal |
Coming Next: Part 3
In the third and final part we’ll cover specialized structures that demonstrate advanced expertise:
- Trie — Autocomplete and prefix search
- Union-Find — Connected components and cycle detection
- Matrix — Dynamic programming and implicit graphs
Which of these structures has given you the most trouble in interviews? Share your experience in the comments.
This article is part of the “Data Structures for Technical Interviews” series on yoDEV. Follow us so you don’t miss the next installment.