ভূমিকা

BFS (Breadth-First Search) এবং DFS (Depth-First Search) হলো Graph এবং Tree traversal-এর দুটি মৌলিক technique। BFS Queue ব্যবহার করে level by level traverse করে, আর DFS Stack (বা recursion) ব্যবহার করে depth-first explore করে। Interview-এ এই দুটি technique-এর উপর অনেক সমস্যা আসে।

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

সমস্যার বিবরণ

একটি binary tree-এর root দেওয়া আছে। Tree-এর সব node-এর value level by level (বাম থেকে ডানে) return করতে হবে।

উদাহরণ:

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: [[3], [9, 20], [15, 7]]
• কারণ: Level 1-এ 3, Level 2-এ 9, 20, Level 3-এ 15, 7

চিন্তার পদ্ধতি

BFS ব্যবহার করব। Queue-এ root দিয়ে শুরু করব। প্রতিটি level-এ সব node process করব এবং তাদের children Queue-এ যোগ করব। প্রতিটি level-এর শুরুতে Queue-এর size জেনে নেব।

সমাধান (Java)

import java.util.*;

public class BinaryTreeLevelOrder {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    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); // Root দিয়ে শুরু

        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // বর্তমান level-এর node সংখ্যা
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                // বাম ও ডান child Queue-এ যোগ করি
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }

    public static void main(String[] args) {
        BinaryTreeLevelOrder solution = new BinaryTreeLevelOrder();

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(solution.levelOrder(root));
        // Output: [[3], [9, 20], [15, 7]]
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(n)

---

সমস্যা ২: Number of Islands (DFS)

সমস্যার বিবরণ

একটি 2D grid দেওয়া আছে যেখানে '1' মানে land এবং '0' মানে water। Grid-এ মোট কতটি island আছে তা বের করতে হবে। Island হলো সংলগ্ন land cell-এর সমষ্টি (উপরে, নিচে, বামে, ডানে)।

উদাহরণ:

• Input:

  11110
  11010
  11000
  00000
  

• Output: 1 (সব land একটি island গঠন করে)
• Input:

  11000
  11000
  00100
  00011
  

• Output: 3

চিন্তার পদ্ধতি

DFS ব্যবহার করব। প্রতিটি '1' cell পেলে island count বাড়াব এবং সেই cell থেকে DFS চালিয়ে সব সংলগ্ন '1' cell-কে '0' করে দেব (visited mark)। এভাবে সব island গণনা করব।

সমাধান (Java)

public class NumberOfIslands {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int islands = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    islands++; // নতুন island পেলাম
                    dfs(grid, r, c); // এই island-এর সব cell mark করি
                }
            }
        }

        return islands;
    }

    private void dfs(char[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Boundary বা water হলে return
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0') return;

        grid[r][c] = '0'; // Visited mark করি

        // চারদিকে DFS চালাই
        dfs(grid, r + 1, c); // নিচে
        dfs(grid, r - 1, c); // উপরে
        dfs(grid, r, c + 1); // ডানে
        dfs(grid, r, c - 1); // বামে
    }

    public static void main(String[] args) {
        NumberOfIslands solution = new NumberOfIslands();

        char[][] grid1 = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        };
        System.out.println(solution.numIslands(grid1)); // Output: 1

        char[][] grid2 = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println(solution.numIslands(grid2)); // Output: 3
    }
}

সময় জটিলতা: O(m × n) | স্থান জটিলতা: O(m × n) (recursion stack)

---

সমস্যা ৩: Word Ladder (BFS — Shortest Path)

সমস্যার বিবরণ

দুটি word beginWord এবং endWord এবং একটি word list wordList দেওয়া আছে। beginWord থেকে endWord-এ পৌঁছাতে সর্বনিম্ন কতটি step লাগবে তা বের করতে হবে। প্রতিটি step-এ শুধু একটি character পরিবর্তন করা যাবে এবং পরিবর্তিত word অবশ্যই wordList-এ থাকতে হবে।

উদাহরণ:

• Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
• Output: 5
• কারণ: "hit" → "hot" → "dot" → "dog" → "cog" (5টি word = 5 step)

চিন্তার পদ্ধতি

BFS ব্যবহার করব কারণ shortest path খুঁজতে হবে। প্রতিটি word থেকে এক character পরিবর্তন করে সম্ভাব্য সব word চেক করব। যদি সেই word wordList-এ থাকে এবং আগে visit না হয়ে থাকে তাহলে Queue-এ যোগ করব।

সমাধান (Java)

import java.util.*;

public class WordLadder {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList); // O(1) lookup-এর জন্য

        if (!wordSet.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        int steps = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            steps++;

            for (int i = 0; i < levelSize; i++) {
                String word = queue.poll();
                char[] chars = word.toCharArray();

                // প্রতিটি position-এ 'a' থেকে 'z' try করি
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];

                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        chars[j] = c;
                        String newWord = new String(chars);

                        if (newWord.equals(endWord)) return steps; // পৌঁছে গেছি!

                        if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                            visited.add(newWord);
                            queue.offer(newWord);
                        }
                    }

                    chars[j] = original; // Reset
                }
            }
        }

        return 0; // endWord-এ পৌঁছানো সম্ভব নয়
    }

    public static void main(String[] args) {
        WordLadder solution = new WordLadder();
        List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
        System.out.println(solution.ladderLength("hit", "cog", wordList)); // Output: 5

        List<String> wordList2 = Arrays.asList("hot","dot","dog","lot","log");
        System.out.println(solution.ladderLength("hit", "cog", wordList2)); // Output: 0
    }
}

সময় জটিলতা: O(M² × N) যেখানে M = word দৈর্ঘ্য, N = wordList size | স্থান জটিলতা: O(M × N)

---

সমস্যা ৪: Clone Graph (DFS)

সমস্যার বিবরণ

একটি undirected graph-এর একটি node দেওয়া আছে। সম্পূর্ণ graph-এর একটি deep copy (clone) তৈরি করতে হবে।

উদাহরণ:

• Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
• Output: Graph-এর একটি সম্পূর্ণ clone যেখানে সব node এবং edge নতুনভাবে তৈরি হয়েছে

চিন্তার পদ্ধতি

DFS এবং HashMap ব্যবহার করব। HashMap-এ original node → cloned node সংরক্ষণ করব। DFS-এ প্রতিটি node-এর জন্য প্রথমে clone তৈরি করব, তারপর তার neighbors recursively clone করব।

সমাধান (Java)

import java.util.*;

public class CloneGraph {
    static class Node {
        int val;
        List<Node> neighbors;
        Node(int val) {
            this.val = val;
            this.neighbors = new ArrayList<>();
        }
    }

    private Map<Node, Node> visited = new HashMap<>(); // original -> clone

    public Node cloneGraph(Node node) {
        if (node == null) return null;

        // এই node আগে clone হয়েছে কিনা চেক করি
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // নতুন clone node তৈরি করি
        Node cloneNode = new Node(node.val);
        visited.put(node, cloneNode); // আগেই map-এ রাখি (cycle handle করতে)

        // প্রতিটি neighbor recursively clone করি
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }

    public static void main(String[] args) {
        CloneGraph solution = new CloneGraph();

        // Graph: 1 -- 2 -- 3 -- 4 -- 1 (cycle)
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        node1.neighbors.addAll(Arrays.asList(node2, node4));
        node2.neighbors.addAll(Arrays.asList(node1, node3));
        node3.neighbors.addAll(Arrays.asList(node2, node4));
        node4.neighbors.addAll(Arrays.asList(node1, node3));

        Node cloned = solution.cloneGraph(node1);
        System.out.println("Cloned node value: " + cloned.val); // Output: 1
        System.out.println("Neighbors: " + cloned.neighbors.size()); // Output: 2
        System.out.println("Same object? " + (cloned == node1)); // Output: false
    }
}

সময় জটিলতা: O(V + E) যেখানে V = vertices, E = edges | স্থান জটিলতা: O(V)

---

সমস্যা ৫: Rotting Oranges (Multi-source BFS)

সমস্যার বিবরণ

একটি m×n grid দেওয়া আছে যেখানে 0 = empty, 1 = fresh orange, 2 = rotten orange। প্রতি মিনিটে rotten orange সংলগ্ন fresh orange-কে রotten করে। সব orange rotten হতে কত মিনিট লাগবে তা বের করতে হবে। যদি সব orange rotten করা সম্ভব না হয় তাহলে -1 return করতে হবে।

উদাহরণ:

• Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
• Output: 4
• Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
• Output: -1 (bottom-left orange isolated)

চিন্তার পদ্ধতি

Multi-source BFS ব্যবহার করব। সব rotten orange একসাথে Queue-এ দিয়ে BFS শুরু করব। প্রতিটি level = 1 মিনিট। শেষে কোনো fresh orange বাকি থাকলে -1 return করব।

সমাধান (Java)

import java.util.*;

public class RottingOranges {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;

        // সব rotten orange Queue-এ দিই এবং fresh count করি
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.offer(new int[]{r, c}); // Rotten orange queue-এ
                } else if (grid[r][c] == 1) {
                    freshCount++; // Fresh orange count
                }
            }
        }

        if (freshCount == 0) return 0; // কোনো fresh orange নেই

        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        int minutes = 0;

        while (!queue.isEmpty() && freshCount > 0) {
            minutes++;
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                int[] cell = queue.poll();

                for (int[] dir : directions) {
                    int nr = cell[0] + dir[0];
                    int nc = cell[1] + dir[1];

                    // Valid cell এবং fresh orange হলে rotten করি
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; // Fresh → Rotten
                        freshCount--;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }

        return freshCount == 0 ? minutes : -1;
    }

    public static void main(String[] args) {
        RottingOranges solution = new RottingOranges();

        int[][] grid1 = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(solution.orangesRotting(grid1)); // Output: 4

        int[][] grid2 = {{2,1,1},{0,1,1},{1,0,1}};
        System.out.println(solution.orangesRotting(grid2)); // Output: -1

        int[][] grid3 = {{0,2}};
        System.out.println(solution.orangesRotting(grid3)); // Output: 0
    }
}

সময় জটিলতা: O(m × n) | স্থান জটিলতা: O(m × n)

---

সারসংক্ষেপ

সমস্যা	Algorithm	Data Structure	সময় জটিলতা	স্থান জটিলতা
Binary Tree Level Order Traversal	BFS	Queue	O(n)	O(n)
Number of Islands	DFS	Recursion Stack	O(m×n)	O(m×n)
Word Ladder	BFS (Shortest Path)	Queue + HashSet	O(M²×N)	O(M×N)
Clone Graph	DFS	HashMap + Recursion	O(V+E)	O(V)
Rotting Oranges	Multi-source BFS	Queue	O(m×n)	O(m×n)

BFS কখন ব্যবহার করবেন: Shortest path, Level-by-level traversal, Minimum steps। DFS কখন ব্যবহার করবেন: Connected components, Cycle detection, Path existence, Graph cloning।

এই দুটি technique আয়ত্ত করলে Graph এবং Tree-এর বেশিরভাগ interview সমস্যা সমাধান করা সম্ভব।