DSA III: Trees, Graphs, BFS/DFS, Recursion & Intervals

Real-world analogy

What is it?

Trees, graphs, BFS/DFS, recursion, and interval problems are the advanced tier of mobile engineering interviews. They require pattern recognition and the ability to trust recursive thinking — skills that come from understanding the structure, not memorizing solutions.

Real-world relevance

In Tixio's workspace hierarchy (workspace → channels → threads → messages), tree traversal computes unread counts by summing up the tree. In FieldBuzz, finding the shortest route between survey locations on a road network is a graph shortest-path problem. Calendar scheduling in any SaaS app uses merge intervals for conflict detection.

Key points

• Binary tree fundamentals — Binary tree: each node has at most 2 children (left, right). BST (Binary Search Tree): left subtree values < node < right subtree values. Dart: class TreeNode { int val; TreeNode? left, right; TreeNode(this.val); }. Height: O(log n) for balanced, O(n) for skewed. Interview key insight: most tree problems are recursive — trust the recursion.
• Tree traversal patterns — Inorder (Left-Root-Right): gives sorted sequence for BST. Preorder (Root-Left-Right): good for tree serialization, copying. Postorder (Left-Right-Root): good for deletion, computing subtree results. Level-order (BFS): good for level-by-level processing. Each is O(n) time O(h) space for recursive (h = height), O(n) for iterative BFS.
• Recursion thinking for trees — Tree recursion template: (1) base case — null node returns base value; (2) recursive calls on left and right subtrees; (3) combine results and return. For maxDepth: if node==null return 0; return 1 + max(maxDepth(node.left), maxDepth(node.right)). Trust that the recursive call returns the correct answer for subtrees — don't try to trace the full call stack.
• BFS with a queue — BFS (Breadth-First Search) explores level by level. Template: Queue q = Queue(); q.add(root); while(q.isNotEmpty){ final node = q.removeFirst(); process(node); if(node.left!=null)q.add(node.left!); if(node.right!=null)q.add(node.right!); }. O(n) time O(w) space where w is max width. Use for: shortest path, level-order traversal, minimum depth.
• DFS patterns — DFS explores as far as possible before backtracking. Recursive DFS is natural for trees. For graphs: track visited Set to avoid cycles. Three DFS patterns: (1) return value from recursion (max depth), (2) pass accumulator down (path sum), (3) use outer variable for global result (diameter of tree). Recognize which pattern the problem needs.
• Graph representation — Adjacency list: Map> graph = {}. Most space-efficient for sparse graphs. Adjacency matrix: List> — O(V²) space, O(1) edge lookup. For interview problems: build the graph first from the input, then run BFS/DFS. Mobile context: user connections, room-device relationships, prerequisite chains.
• Graph BFS: shortest path — BFS guarantees shortest path in unweighted graphs. Level = distance from source. Template: Queue q with source; Set visited = {source}; int steps = 0; while q not empty: process level (all nodes at current distance), increment steps, add unvisited neighbors. This level-by-level processing is the key insight.
• Merge intervals pattern — Sort intervals by start time. Iterate: if current interval overlaps previous (current.start <= prev.end), merge by extending prev.end = max(prev.end, current.end). Else add prev to result and move to current. O(n log n) for sort + O(n) for merge = O(n log n). Mobile context: calendar event overlap detection, time slot availability.
• Meeting rooms pattern — Given intervals representing meeting times, can one person attend all? Sort by start time. Check if any adjacent pair overlaps: meetings[i].start < meetings[i-1].end. If yes: conflict. O(n log n). Extension: minimum rooms needed — use a min-heap of end times; greedily assign to earliest-ending room or open a new one.
• Recursion vs iteration — Recursion is elegant but uses O(h) stack space — can stack overflow on deep inputs (h=10K). Iterative DFS using an explicit stack avoids this. For interviews: start with recursion (easier to explain), then mention 'for production I'd consider iterative to avoid stack overflow on degenerate inputs.' Shows seniority.
• Interview strategy for hard problems — Hard DSA problems feel impossible until you see the pattern. Steps: (1) Draw an example — visualize the data structure. (2) Identify traversal pattern (BFS/DFS/recursion?). (3) Write the base case first. (4) Trust recursion — write the recursive case assuming subtree calls work. (5) Trace through the example. (6) Code. Interviewers want to see your thinking process, not just the answer.
• Complexity for trees and graphs — Tree traversal: O(n) time, O(h) space recursive (O(log n) balanced, O(n) skewed). BFS: O(V+E) time, O(V) space. DFS: O(V+E) time, O(V) space. Merge intervals: O(n log n). Always state complexity — for trees, mention that the space is O(h) not O(n) for balanced trees, and explain when that distinction matters.

Code example

// Tree: max depth (recursive)
int maxDepth(TreeNode? node) {
  if (node == null) return 0;
  return 1 + [maxDepth(node.left), maxDepth(node.right)].reduce((a,b) => a>b?a:b);
}

// Tree: level-order traversal (BFS)
import 'dart:collection';
List<List<int>> levelOrder(TreeNode? root) {
  if (root == null) return [];
  final result = <List<int>>[];
  final q = Queue<TreeNode>()..add(root);
  while (q.isNotEmpty) {
    final level = <int>[];
    final size = q.length;
    for (int i = 0; i < size; i++) {
      final node = q.removeFirst();
      level.add(node.val);
      if (node.left != null) q.add(node.left!);
      if (node.right != null) q.add(node.right!);
    }
    result.add(level);
  }
  return result;
}

// Graph: BFS shortest path
int shortestPath(Map<int,List<int>> graph, int src, int dst) {
  final visited = <int>{src};
  final q = Queue<int>()..add(src);
  int steps = 0;
  while (q.isNotEmpty) {
    final size = q.length;
    for (int i = 0; i < size; i++) {
      final node = q.removeFirst();
      if (node == dst) return steps;
      for (final neighbor in graph[node] ?? []) {
        if (visited.add(neighbor)) q.add(neighbor);
      }
    }
    steps++;
  }
  return -1;
}

// Merge intervals
List<List<int>> mergeIntervals(List<List<int>> intervals) {
  intervals.sort((a, b) => a[0].compareTo(b[0]));
  final result = <List<int>>[intervals[0]];
  for (final curr in intervals.skip(1)) {
    if (curr[0] <= result.last[1]) {
      result.last[1] = result.last[1] > curr[1] ? result.last[1] : curr[1];
    } else {
      result.add(curr);
    }
  }
  return result;
}

Line-by-line walkthrough

1. 1. maxDepth base case: null node contributes 0 to depth
2. 2. Recursive case: 1 (current node) plus the deeper of left and right subtrees
3. 3. This single line encodes the entire depth computation — trust the recursion
4. 4. levelOrder uses BFS with a queue to process nodes level by level
5. 5. The inner for loop processes exactly one level per outer while iteration
6. 6. q.length captured before the inner loop — nodes added during iteration are next level
7. 7. shortestPath BFS increments steps after processing each complete level
8. 8. visited.add() returns false if element already in set — prevents revisiting
9. 9. mergeIntervals sorts first so overlapping intervals are guaranteed adjacent
10. 10. Last interval in result is extended if current interval overlaps it
11. 11. result.last[1] = max of both ends handles the case where current is fully contained

Spot the bug

// Check if a binary tree is symmetric
bool isSymmetric(TreeNode? root) {
  return isMirror(root, root);
}
bool isMirror(TreeNode? left, TreeNode? right) {
  if (left == null && right == null) return true;
  if (left == null || right == null) return false;
  return left.val == right.val
    && isMirror(left.left, right.left)
    && isMirror(left.right, right.right);
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• LeetCode Explore: Binary Tree (leetcode.com)
• NeetCode — Trees and Graphs (neetcode.io)
• Visualgo — Tree and Graph Visualizations (visualgo.net)
• LeetCode Interval Problems (leetcode.com)