Tree & Graph Interview Problems — Complete Solutions Guide
In this tutorial, you'll learn about Tree & Graph Interview Problems. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Tree and graph problems test your understanding of recursive and iterative traversal, pathfinding, and connected-component analysis. These appear in 40% of on-site interviews at top tech companies.
Learning Path
flowchart LR A["Linked List Problems"] --> B["Tree & Graph Problems
You are here"] B --> C["DP Problems"] C --> D["System Design Prep"] style B fill:#f90,color:#fff,stroke-width:2px
Binary Tree Traversals
In-order, pre-order, and post-order traversals are the foundation of tree problems.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root):
result = []
def dfs(node):
if not node:
return
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
return result
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(inorder_traversal(root))
[1, 3, 2]
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public class TreeTraversal {
public static void inorder(TreeNode root, List<Integer> result) {
if (root == null) return;
inorder(root.left, result);
result.add(root.val);
inorder(root.right, result);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
List<Integer> result = new ArrayList<>();
inorder(root, result);
System.out.println(result);
}
}
[1, 3, 2]
#include <vector>
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorder(TreeNode* root, vector<int>& result) {
if (!root) return;
inorder(root->left, result);
result.push_back(root->val);
inorder(root->right, result);
}
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
vector<int> result;
inorder(root, result);
for (int v : result) cout << v << " ";
return 0;
}
1 3 2
Graph BFS: Shortest Path in Unweighted Graph
BFS finds the shortest path in an unweighted graph by exploring nodes level by level.
from collections import deque
def shortest_path(graph, start, target):
visited = {start}
queue = deque([(start, 0)])
while queue:
node, dist = queue.popleft()
if node == target:
return dist
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1, 5],
5: [2, 4]
}
print(shortest_path(graph, 0, 5))
2
import java.util.*;
public class GraphBFS {
public static int shortestPath(Map<Integer, List<Integer>> graph, int start, int target) {
Set<Integer> visited = new HashSet<>();
Queue<int[]> queue = new LinkedList<>();
visited.add(start);
queue.offer(new int[]{start, 0});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int node = curr[0], dist = curr[1];
if (node == target) return dist;
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(new int[]{neighbor, dist + 1});
}
}
}
return -1;
}
}
Depth-First Search: Number of Islands
DFS explores all connected nodes in a grid by recursively visiting neighbors.
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
print(num_islands(grid))
3
Topological Sort (Kahn's Algorithm)
Topological sort orders nodes in a DAG such that every edge goes from earlier to later nodes.
from collections import deque
def topological_sort(num_nodes, edges):
in_degree = [0] * num_nodes
adj = [[] for _ in range(num_nodes)]
for u, v in edges:
adj[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in adj[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result if len(result) == num_nodes else []
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
print(topological_sort(4, edges))
[0, 1, 2, 3]
Common Mistakes
- Visited set placement in BFS — Mark visited when adding to the queue, not when polling. Poll-time marking causes duplicate enqueues.
- Infinite Recursion in DFS — Without cycle detection, DFS on cyclic graphs never terminates. Always track the current path for directed graphs.
- Null pointer on leaf children — Always check
node.leftandnode.rightfor null before accessing their values in tree traversals. - Assuming Binary Search Tree — Not all binary trees are BSTs. Do not apply BST assumptions to general Binary Tree problems.
- Forgetting to handle disconnected graphs — BFS/DFS from a single node only explores one component. Iterate over all nodes for island-counting style problems.
- Incorrect level tracking in BFS — Use a per-level loop or store distance in the queue tuple. Incrementing a counter per-iteration without level boundaries gives wrong distances.
- Stack overflow in deep Recursion — Recursive DFS on deep trees (10k+ nodes) may overflow the call stack. Use iterative DFS with an explicit stack for production-readiness.
Practice Questions
1. Find the lowest common ancestor of two nodes in a Binary Tree.
Traverse recursively. If both nodes are in the left subtree, recurse left. If both are right, recurse right. Otherwise, current node is the LCA.
2. Clone a graph using BFS or DFS.
Use a hash map from original node to cloned node. For BFS, process neighbors level by level, cloning and connecting as you go.
3. Challenge: Word Ladder (Leetcode 127)
Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, with each intermediate word in the dictionary.
FAQ
Related Tutorials
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-23.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro