🚀 Blog 4: Trees & Graphs — Expedia DSA Prep

Expedia often tests binary tree traversal, root-to-leaf computations, and graph connectivity problems.
We’ll cover:

Vertical Order Traversal of Binary Tree
Maximum Root-to-Leaf Path Sum
Number of Islands (Grid DFS/BFS)

🔹 Problem 1: Vertical Order Traversal of Binary Tree

Pattern: BFS with column indexing

📌 Traverse nodes column by column (like reading tree vertically).

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class VerticalTraversal {
    static class Pair {
        TreeNode node;
        int col;
        Pair(TreeNode n, int c) { node = n; col = c; }
    }

    public static List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();

        Map<Integer, List<Integer>> map = new TreeMap<>();
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(root, 0));

        while (!q.isEmpty()) {
            Pair p = q.poll();
            map.computeIfAbsent(p.col, k -> new ArrayList<>()).add(p.node.val);

            if (p.node.left != null) q.offer(new Pair(p.node.left, p.col - 1));
            if (p.node.right != null) q.offer(new Pair(p.node.right, p.col + 1));
        }

        return new ArrayList<>(map.values());
    }
}

✅ Time Complexity: O(N log N) (due to TreeMap)

🔹 Problem 2: Maximum Root-to-Leaf Path Sum

Pattern: DFS with accumulation

📌 Find max sum from root node to any leaf node.

public class MaxRootToLeafSum {
    public static int maxPathSum(TreeNode root) {
        if (root == null) return Integer.MIN_VALUE;
        if (root.left == null && root.right == null) return root.val;

        int left = maxPathSum(root.left);
        int right = maxPathSum(root.right);

        return root.val + Math.max(left, right);
    }
}

✅ Time Complexity: O(N)

🔹 Problem 3: Number of Islands (Graph DFS/BFS)

Pattern: Flood Fill DFS/BFS

📌 Count connected groups of 1s in a 2D grid.

public class NumberOfIslands {
    public static int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private static void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0')
            return;

        grid[i][j] = '0'; // mark visited
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}