Trees and Graphs Interview Questions for C Programming with DSA
25 Trees and Graphs questions with answers for c programming with dsa roles — 6 easy, 11 medium, 8 hard.
About Trees and Graphs
Trees and graphs appear in mid and senior level coding rounds. Learn binary trees, traversals, binary search trees, balanced trees, tries, graph representations, BFS and DFS, shortest paths with Dijkstra and Bellman-Ford, topological sort, union-find and grid problems like counting islands, all implemented in C.
Sheet progressStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
✓ 3 questions free • Unlock the rest in seconds
01
What is a binary search tree and what are its operation costs?
A binary search tree keeps every node's left subtree smaller and right subtree larger than the node. Search, insert and delete follow one path from the root, so they cost O(h), where h is the height. A balanced tree has h of about log n, but inserting sorted data creates a skewed tree with h equal to n. In-order traversal of a BST gives keys in sorted order.
In-order visits left, node, right and gives sorted output for a BST. Pre-order visits node, left, right and is used to copy or serialise a tree. Post-order visits left, right, node and is used to delete a tree or evaluate expression trees. Level-order visits nodes level by level using a queue. The first three are depth first and use recursion or an explicit stack.
03
What is the difference between a complete, full and perfect binary tree?
A full binary tree has every node with zero or two children. A complete binary tree has all levels filled except possibly the last, which is filled from left to right; heaps use this shape so they fit an array. A perfect binary tree has all internal nodes with two children and all leaves at the same level, so it has 2 to the power h+1 minus 1 nodes.
04
Insert a value into a binary search tree recursively in C.
Height is one plus the larger subtree height.
int height(const TNode *root) {
if (root == NULL) return 0;
int lh = height(root->left);
int rh = height(root->right);
return 1 + (lh > rh ? lh : rh);
}
This counts nodes on the longest root to leaf path; return -1 for empty trees if height is defined in edges. Time O(n).
06
How do you explain the time complexity of your solution to an interviewer?
Situation: in a technical round I solved a tree problem but the interviewer questioned its efficiency. Task: justify the complexity clearly. Action: I explained that each node is visited once and does constant work, so time is O(n), and that recursion depth equals tree height, giving O(h) space, worst case O(n) for a skewed tree. Result: the interviewer agreed and moved to a harder follow-up.
07
Why are self-balancing trees like AVL and red-black trees needed?
A plain BST can degrade to a linked list with O(n) operations when data arrives in sorted order. AVL trees keep the height difference of subtrees at most one using rotations, giving faster lookups. Red-black trees use colour rules with looser balance, so inserts and deletes need fewer rotations. Both guarantee O(log n). Red-black trees are used in the Linux kernel, C++ std::map and Java TreeMap.
An adjacency matrix is a V by V array where cell [u][v] marks an edge; it gives O(1) edge checks but uses O(V squared) memory, suiting dense graphs. An adjacency list stores for each vertex a list or dynamic array of neighbours, using O(V + E) memory, which suits sparse real world graphs like road or social networks. Weighted graphs store the weight with each edge.
BFS explores level by level using a queue and finds the shortest path in unweighted graphs. DFS goes deep along one path using recursion or a stack, and suits cycle detection, topological sort, connected components and backtracking. Both run in O(V + E). BFS may use more memory on wide graphs, while recursive DFS can overflow the call stack on very deep graphs.
10
A recursive tree traversal crashes on a very large, skewed tree. How do you fix it?
A skewed tree has height close to n, so recursion depth becomes huge and overflows the call stack. Convert the traversal to an iterative version using an explicit stack allocated on the heap, or use Morris traversal for in-order with O(1) extra space. Long term, use a self-balancing tree so height stays around log n.
11
You need to find the shortest route between two cities on a map with distances. Which algorithm do you use and why?
Road distances are non-negative, so Dijkstra's algorithm with a min heap is the right choice, giving O((V + E) log V). If you only need one target, stop when it is popped from the heap. For very large maps, A star with a straight-line distance heuristic explores fewer nodes. If some edges had negative costs, Bellman-Ford would be needed.
12
Count the number of islands in a grid of land and water cells. What approach do you take?
Treat each land cell as a graph node connected to its four neighbours. Scan the grid, and when you find unvisited land, increment the count and flood fill with DFS or BFS to mark the whole island visited. Time and space are O(rows times cols). For very large grids, use iterative BFS to avoid recursion depth issues, or union-find.
13
How would you check whether a binary tree is a valid BST?
Comparing each node only with its children is wrong, because a deeper node can break the rule. Pass a valid range down: the left child must be in (min, node value) and the right child in (node value, max), starting with the full range of long long. Alternatively, do an in-order traversal and check values are strictly increasing. Both are O(n).
14
Write BFS on a graph stored as an adjacency matrix.
Use a queue and a visited array.
void bfs(int n, int adj[n][n], int start) {
int visited[n], queue[n], front = 0, rear = 0;
for (int i = 0; i < n; i++) visited[i] = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int u = queue[front++];
printf("%d ", u);
for (int v = 0; v < n; v++) {
if (adj[u][v] && !visited[v]) {
visited[v] = 1;
queue[rear++] = v;
}
}
}
}
15
Find the lowest common ancestor of two nodes in a binary search tree.
Use the BST order to walk down from the root.
TNode *lcaBST(TNode *root, int a, int b) {
while (root) {
if (a < root->key && b < root->key) root = root->left;
else if (a > root->key && b > root->key) root = root->right;
else return root;
}
return NULL;
}
The first node where a and b split is the LCA. Time O(h) and space O(1).
16
Tell me about a project where you applied graph algorithms.
Situation: our college fest needed a campus navigation kiosk. Task: give the shortest walking route between buildings. Action: I modelled buildings and paths as a weighted graph in C, implemented Dijkstra with a binary heap and added a simple text interface showing turn by turn directions. Result: the kiosk answered routes instantly for 40 locations and over 2000 visitors used it.
17
What is a trie and when is it better than a hash table?
A trie is a tree where each edge represents a character, so words sharing a prefix share a path. Lookup and insert take O(L) for a word of length L, independent of how many words are stored. It beats a hash table for prefix queries such as autocomplete, spell checking and longest prefix matching in IP routing. The trade-off is higher memory use from many child pointers.
Dijkstra finds shortest paths from a source in a graph with non-negative edge weights. It keeps tentative distances, repeatedly takes the unvisited vertex with the smallest distance from a min heap and relaxes its edges, updating neighbours if a shorter path is found. With a binary heap it runs in O((V + E) log V). It fails with negative weights, where Bellman-Ford is used instead.
A topological sort orders the vertices of a directed acyclic graph so every edge goes from earlier to later. Kahn's algorithm repeatedly removes vertices with zero in-degree using a queue; DFS adds vertices to the order after finishing their descendants. If not all vertices are processed, the graph has a cycle. It is used for build systems, course prerequisites and task scheduling.
Union-find, or disjoint set union, tracks which elements are in the same group. find returns a group's representative and union merges two groups. With path compression and union by rank, both run in nearly constant amortised time. It is used for Kruskal's minimum spanning tree, detecting cycles in undirected graphs and counting connected components in dynamic connectivity problems.
21
A build tool must compile modules in the correct dependency order and report circular dependencies. How would you design it?
Model modules as vertices and dependencies as directed edges, then run Kahn's topological sort. Start with modules that have zero in-degree, process them in a queue and reduce in-degrees of dependants. Modules left unprocessed form a cycle, which you report by tracing them with DFS. Independent modules at the same stage can be compiled in parallel.
22
A social network feature must suggest friends of friends. How would you find them efficiently?
Represent users and friendships as an undirected graph with adjacency lists. Run BFS from the user to depth two, collect nodes at distance exactly two and rank them by the number of mutual friends counted during traversal. Exclude existing friends. For huge graphs, precompute suggestions offline in batches and cap the number of neighbours explored per user.
23
Implement union-find with path compression and union by rank.
Two small functions cover most uses.
int parent[MAXN], rnk[MAXN];
void makeSet(int n) {
for (int i = 0; i < n; i++) { parent[i] = i; rnk[i] = 0; }
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
int unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return 0;
if (rnk[a] < rnk[b]) { int t = a; a = b; b = t; }
parent[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
return 1;
}
24
Describe a time you had to make a trade-off between memory and speed.
Situation: a C routing service on a small server ran out of memory with an adjacency matrix for 50,000 nodes. Task: fit within 512 MB without slowing queries much. Action: I switched to compact adjacency lists stored in flat arrays, known as CSR format, and kept a small cache for frequent routes. Result: memory fell from 10 GB worth of matrix to 60 MB and queries stayed under 20 ms.
25
A Dijkstra implementation gives wrong distances on a graph with a few negative edges. Why?
Dijkstra assumes that once a vertex is taken from the heap its distance is final, which holds only when all weights are non-negative. A negative edge found later can make a shorter path, so results are wrong. Use Bellman-Ford, which relaxes all edges V-1 times in O(VE) and can also detect negative cycles, or reweight the graph with Johnson's algorithm.
Frequently asked questions
How important is Trees and Graphs in C Programming with DSA interviews?
Trees and graphs appear in mid and senior level coding rounds. Learn binary trees, traversals, binary search trees, balanced trees, tries, graph representations, BFS and DFS, shortest paths with Dijkstra and Bellman-Ford, topological sort, union-find and grid problems like counting islands, all implemented in C.
How should I use the Trees and Graphs sheet?
Go top to bottom — easy to hard. Answer before opening each answer, tick what you solved and save misses to Last-Minute Revision.