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

Real-world analogy

What is it?

Trees and graphs are the data structures underlying most complex real-world systems — file systems, network routing, dependency management, social graphs, and Android's view hierarchy. BFS and DFS are the two fundamental algorithms for exploring these structures. Mastering them means recognizing when a problem is really a graph traversal in disguise (even when it does not say 'graph' explicitly — like grid island counting or course scheduling).

Real-world relevance

In FieldBuzz's field officer management system, the organizational hierarchy (manager → area manager → officer) was modeled as a tree. Computing 'total records submitted by all officers under a manager' was a postorder tree traversal — gather results from all children, then combine at the parent. This is the exact same pattern as computing subtree sums in a BST interview problem.

Key points

• Binary Tree Traversal — Inorder, Preorder, Postorder — Inorder (left, root, right): for a BST, this gives elements in sorted order. Preorder (root, left, right): useful for serializing a tree. Postorder (left, right, root): useful for deleting a tree or computing subtree results bottom-up. All are O(n) time, O(h) space where h is tree height (O(log n) balanced, O(n) skewed).
• Tree Recursion Pattern — Most tree problems follow: base case (null node returns a neutral value), recursive case (compute result for left subtree, compute for right subtree, combine with current node). Examples: max depth (1 + max(left, right)), has path sum (target == node.val if leaf, or recurse with target - node.val). Trust the recursion — do not trace the full tree mentally.
• BST Properties and Operations — A Binary Search Tree satisfies: all left descendants < node.val < all right descendants. Search is O(log n) for balanced BST. Insert follows the same path as search — go left if smaller, right if larger. In-order traversal of BST gives sorted sequence. Common interview: validate a BST by passing valid range (min, max) bounds down the recursion.
• Level-Order BFS (Tree) — Process tree level by level using a Queue. Enqueue root. While queue is not empty: record the queue size (nodes in current level), dequeue exactly that many nodes, process each, enqueue their children. After inner loop, one full level is processed. Used for: minimum depth, right side view, zigzag traversal, connect next right pointers.
• Graph Representation — Most interview graphs are given as adjacency lists: Map> or built from an edge list. For grid problems (islands, shortest path), the graph is implicit — each cell is a node, 4 or 8 neighbors are edges. Weighted graphs use Map>> where the pair is (neighbor, weight). Always ask if the graph is directed or undirected, and whether it can have cycles.
• BFS on Graphs — Shortest Path (Unweighted) — BFS gives the shortest path in terms of number of edges in an unweighted graph. Template: queue + visited set. Enqueue start node, mark visited. While queue not empty: dequeue node, check if it is the goal, enqueue unvisited neighbors and mark them visited. Level tracking: use a step counter incremented each level. O(V + E) time and space.
• DFS on Graphs — Connectivity and Paths — DFS explores a path to its end before backtracking. Iterative DFS: use a Stack (push start, while stack not empty: pop, process, push unvisited neighbors). Recursive DFS: call DFS on each unvisited neighbor after marking current as visited. Use for: detect connected components, topological sort, check if path exists. O(V + E) time and space.
• Number of Islands — Grid BFS/DFS Classic — Given a 2D grid of '1' (land) and '0' (water), count islands. Iterate all cells. When you find an unvisited '1', increment island count and BFS/DFS to mark all connected '1's as visited. Each BFS/DFS call floods an entire island. O(m*n) time — every cell is visited at most once. Classic example of implicit graph (grid as adjacency list).
• Recursion — Trust the Call Stack — Recursive thinking: define what your function returns (e.g. 'the max depth rooted at this node'), then assume the recursive calls are correct, and combine. Do not mentally simulate the full call tree — that way lies madness. The three laws: base case must exist, each call must make progress toward the base case, and the combination step must be correct.
• Merge Intervals — Given a list of intervals [start, end], merge all overlapping ones. Sort by start time: O(n log n). Then iterate: if current interval overlaps with last merged (current.start <= last.end), merge by updating last.end = max(last.end, current.end). Otherwise add current to result. Result is O(n). Key insight: after sorting, overlaps are always between adjacent intervals.
• Topological Sort (BFS — Kahn's Algorithm) — For a Directed Acyclic Graph (DAG), find a valid ordering where all edges go from earlier to later in the ordering. Build in-degree count for each node. Enqueue all nodes with in-degree 0. While queue not empty: dequeue node, add to result, decrement in-degree of neighbors, enqueue any neighbor whose in-degree drops to 0. If result has all nodes, no cycle. Used for: course prerequisites, build dependency ordering.
• Pattern Recognition — Tree vs Graph — Tree: connected, n nodes, n-1 edges, no cycles, has a root — use recursion or BFS level-order. Graph: may have cycles, may be disconnected, use a visited set — use BFS for shortest path, DFS for connectivity. Grid problems: always BFS/DFS with 4-directional neighbors, mark visited by modifying the grid in-place or using a visited boolean array.

Code example

// ─── BINARY TREE NODE ───
class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

// ─── INORDER TRAVERSAL (O(n)) ───
fun inorder(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    fun dfs(node: TreeNode?) {
        if (node == null) return
        dfs(node.left)
        result.add(node.value)
        dfs(node.right)
    }
    dfs(root)
    return result
}

// ─── MAX DEPTH (Recursive, O(n)) ───
fun maxDepth(root: TreeNode?): Int {
    if (root == null) return 0
    return 1 + maxOf(maxDepth(root.left), maxDepth(root.right))
}

// ─── LEVEL-ORDER BFS (O(n)) ───
fun levelOrder(root: TreeNode?): List<List<Int>> {
    if (root == null) return emptyList()
    val result = mutableListOf<List<Int>>()
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val levelSize = queue.size
        val level = mutableListOf<Int>()
        repeat(levelSize) {
            val node = queue.removeFirst()
            level.add(node.value)
            node.left?.let { queue.addLast(it) }
            node.right?.let { queue.addLast(it) }
        }
        result.add(level)
    }
    return result
}

// ─── NUMBER OF ISLANDS (Grid DFS, O(m*n)) ───
fun numIslands(grid: Array<CharArray>): Int {
    var count = 0
    fun dfs(r: Int, c: Int) {
        if (r < 0 || r >= grid.size || c < 0 || c >= grid[0].size) return
        if (grid[r][c] != '1') return
        grid[r][c] = '0' // mark visited by sinking the island
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
    }
    for (r in grid.indices) {
        for (c in grid[0].indices) {
            if (grid[r][c] == '1') { count++; dfs(r, c) }
        }
    }
    return count
}

// ─── MERGE INTERVALS (O(n log n)) ───
fun merge(intervals: Array<IntArray>): Array<IntArray> {
    intervals.sortBy { it[0] } // sort by start time
    val merged = mutableListOf<IntArray>()
    for (interval in intervals) {
        if (merged.isEmpty() || merged.last()[1] < interval[0]) {
            merged.add(interval) // no overlap
        } else {
            merged.last()[1] = maxOf(merged.last()[1], interval[1]) // merge
        }
    }
    return merged.toTypedArray()
}

Line-by-line walkthrough

1. 1. inorder uses a nested 'dfs' function — Kotlin allows local function definitions inside other functions, which is clean for recursive helpers that need access to the result list.
2. 2. maxDepth is the purest recursive tree solution: null returns 0 (base case), non-null returns 1 (this node) plus the maximum of its children's depths. Three lines, perfectly expressive.
3. 3. levelOrder records queue.size before the inner repeat loop — this is the number of nodes at the current level. As children are added to the queue during the loop, queue.size grows, but the repeat count is already fixed.
4. 4. node.left?.let { queue.addLast(it) } uses Kotlin's safe-call with let — if left is null, nothing happens. Cleaner than an explicit null check.
5. 5. numIslands modifies the grid in-place by setting visited '1' cells to '0' — this is the 'sinking island' trick that avoids an O(m*n) visited array. Only acceptable if modifying input is allowed (confirm with interviewer).
6. 6. The four DFS calls in numIslands explore all 4-directional neighbors — up, down, left, right. The boundary check 'r = grid.size' is the base case that prevents array out-of-bounds.
7. 7. merge sorts intervals by start time first. Then the merge condition is: if the current interval's start is greater than the last merged interval's end, there is no overlap — add a new interval.
8. 8. When there is overlap (current.start <= last.end), we take the maximum of the two end times — because one interval might be entirely contained within another (e.g. [1,10] and [2,5] merge to [1,10], not [1,5]).

Spot the bug

fun maxDepth(root: TreeNode?): Int {
    if (root == null) return 0
    val left = maxDepth(root.left)
    val right = maxDepth(root.right)
    return maxOf(left, right)
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• LeetCode — Number of Islands (LeetCode)
• LeetCode — Merge Intervals (LeetCode)
• LeetCode — Binary Tree Level Order Traversal (LeetCode)
• Neetcode — Trees and Graphs Patterns (Neetcode)
• LeetCode — Course Schedule (Topological Sort) (LeetCode)