BFS/DFS সম্পর্কিত ৫টি সহজ কোডিং সমস্যা ও সমাধান

ভূমিকা

BFS (Breadth-First Search) এবং DFS (Depth-First Search) হলো graph ও tree traversal-এর দুটি মৌলিক অ্যালগরিদম। ইন্টারভিউতে এগুলো সবচেয়ে বেশি জিজ্ঞাসিত বিষয়গুলোর একটি। নিচে ৫টি Easy স্তরের BFS/DFS সমস্যা Java সমাধান ও বাংলা ব্যাখ্যা সহ দেওয়া হলো।

BFS বনাম DFS — দ্রুত পর্যালোচনা

বৈশিষ্ট্য	BFS	DFS
Data Structure	Queue	Stack (বা Recursion)
Traversal	Level by level	গভীরে যায় প্রথমে
Shortest Path	হ্যাঁ (unweighted graph-এ)	না
Memory	বেশি লাগে	কম লাগে
ব্যবহার	Shortest path, Level order	Connected components, Cycle detection

সমস্যা ১: Binary Tree-র Level Order Traversal (BFS)

সমস্যা: একটি Binary Tree-র সমস্ত node-কে level অনুযায়ী (উপর থেকে নিচে, বাম থেকে ডানে) একটি 2D list-এ সাজিয়ে দিন।

উদাহরণ:

Input Tree:
        3
       / \
      9  20
        /  \
       15   7

Output: [[3], [9, 20], [15, 7]]

চিন্তার ধাপ:

BFS ব্যবহার করব কারণ এটি level by level traverse করে
Queue-তে root রেখে শুরু করব
প্রতিটি level-এ Queue-তে কতটি node আছে সেটা গণনা করব
সেই সংখ্যা অনুযায়ী node বের করে তাদের children Queue-তে যোগ করব

Java সমাধান:

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null)  queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(currentLevel);
        }
        return result;
    }
}

জটিলতা: Time O(n), Space O(n)

মূল কৌশল: queue.size() প্রতিটি iteration-এর শুরুতে store করতে হবে — এটি সেই level-এর মোট node সংখ্যা নির্ধারণ করে।

সমস্যা ২: Binary Tree-র Maximum Depth (DFS)

সমস্যা: একটি Binary Tree-র সর্বোচ্চ গভীরতা (maximum depth) বের করুন।

উদাহরণ:

Input:
    3
   / \
  9  20
    /  \
   15   7

Output: 3

চিন্তার ধাপ:

DFS ব্যবহার করব — recursively গভীরে যাব
প্রতিটি node-এ বাম ও ডান subtree-র depth বের করব
সর্বোচ্চটি নিয়ে ১ যোগ করে return করব

Java সমাধান:

class Solution {
    // Recursive DFS
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth  = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    // Iterative BFS alternative
    public int maxDepthBFS(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left  != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return depth;
    }
}

জটিলতা: Time O(n), Space O(h) যেখানে h = tree height

মূল কৌশল: Recursive DFS-এ max(left, right) + 1 pattern — null node-এ 0 return করা।

সমস্যা ৩: Flood Fill অ্যালগরিদম (DFS on Grid)

সমস্যা: একটি 2D image grid-এ starting pixel (sr, sc) থেকে একই রঙের সংলগ্ন সব pixel-কে নতুন color দিয়ে fill করুন।

উদাহরণ:

Input:  [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2
Output: [[2,2,2],[2,2,0],[2,0,1]]

চিন্তার ধাপ:

Starting pixel-এর original color মনে রেখে DFS শুরু করব
প্রতিটি step-এ 4 দিকে check করব (উপর, নিচ, বাম, ডান)
Edge case: শুরুর pixel ইতিমধ্যে নতুন color হলে কিছু করতে হবে না

Java সমাধান:

class Solution {
    private int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) return image;
        dfs(image, sr, sc, originalColor, color);
        return image;
    }

    private void dfs(int[][] image, int row, int col,
                     int originalColor, int newColor) {
        if (row < 0 || row >= image.length ||
            col < 0 || col >= image[0].length ||
            image[row][col] != originalColor) {
            return;
        }

        image[row][col] = newColor; // fill করো

        for (int[] dir : directions) {
            dfs(image, row + dir[0], col + dir[1], originalColor, newColor);
        }
    }
}

জটিলতা: Time O(m×n), Space O(m×n)

মূল কৌশল: directions array দিয়ে 4 দিক handle করুন। visited tracking-এর জন্য color পরিবর্তনই যথেষ্ট — আলাদা visited array দরকার নেই।

সমস্যা ৪: Graph-এ Connected Components গোনা (DFS)

সমস্যা: n টি node এবং edges array দেওয়া আছে। Undirected graph-এ মোট কতটি connected component আছে বের করুন।

উদাহরণ:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
(Component 1: 0-1-2,  Component 2: 3-4)

চিন্তার ধাপ:

Adjacency List তৈরি করব
প্রতিটি unvisited node থেকে DFS শুরু করব
প্রতিটি নতুন DFS শুরু = একটি নতুন component

Java সমাধান:

import java.util.*;

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        int components = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++;
                dfs(graph, visited, i);
            }
        }
        return components;
    }

    private void dfs(List<List<Integer>> graph,
                     boolean[] visited, int node) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) dfs(graph, visited, neighbor);
        }
    }
}

জটিলতা: Time O(V+E), Space O(V+E)

মূল কৌশল: visited[] array দিয়ে track করা। প্রতিটি unvisited node-এ নতুন DFS শুরু = একটি নতুন component আবিষ্কার।

সমস্যা ৫: Binary Tree Symmetric কিনা যাচাই (DFS)

সমস্যা: একটি Binary Tree তার নিজের mirror image কিনা নির্ধারণ করুন।

উদাহরণ:

Symmetric → true:       Not Symmetric → false:
        1                       1
       / \                     / \
      2   2                   2   2
     / \ / \                   \   \
    3  4 4  3                   3   3

চিন্তার ধাপ:

Root-এর বাম ও ডান subtree mirror কিনা check করব
Mirror মানে: বাম-এর বাম = ডান-এর ডান, বাম-এর ডান = ডান-এর বাম

Java সমাধান:

import java.util.*;

class Solution {
    // Recursive DFS
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean 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.right)
            && isMirror(left.right, right.left);
    }

    // Iterative BFS approach
    public boolean isSymmetricBFS(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode left  = queue.poll();
            TreeNode right = queue.poll();

            if (left == null && right == null) continue;
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;

            // Mirror জোড়া যোগ করো
            queue.offer(left.left);  queue.offer(right.right);
            queue.offer(left.right); queue.offer(right.left);
        }
        return true;
    }
}

জটিলতা: Time O(n), Space O(n)

মূল কৌশল: জোড়ায় জোড়ায় compare — (left.left, right.right) এবং (left.right, right.left) এই cross-compare pattern মনে রাখুন।

সব সমস্যার সারসংক্ষেপ

সমস্যা	অ্যালগরিদম	Time	Space	মূল কৌশল
Level Order Traversal	BFS	O(n)	O(n)	Queue + level size store করা
Maximum Depth	DFS Recursive	O(n)	O(h)	max(left, right) + 1
Flood Fill	DFS on Grid	O(m×n)	O(m×n)	directions array, color = visited
Connected Components	DFS + visited[]	O(V+E)	O(V+E)	unvisited = new component
Symmetric Tree	DFS Mirror check	O(n)	O(n)	cross-compare জোড়ায়

ইন্টারভিউ টিপস

BFS কখন ব্যবহার করবেন: Shortest path, Level order processing, Minimum steps/distance।

DFS কখন ব্যবহার করবেন: Backtracking, Path finding, Cycle detection, Tree height/depth।

সাধারণ Template:

// DFS Template (Graph)
void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) dfs(neighbor, visited, graph);
    }
}

// BFS Template (Graph)
void bfs(int start, List<List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];
    queue.offer(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}