৫টি সহজ Tree কোডিং প্রবলেম ও সমাধান (Java)

ইন্টারভিউতে Tree প্রবলেমের ৯০% এই প্যাটার্নগুলোর উপর দাঁড়িয়ে থাকে। প্রতিটি প্রবলেমে আগে নিজে চেষ্টা করুন, তারপর সমাধান দেখুন।

সব প্রবলেমে এই TreeNode ক্লাসটি ব্যবহার হবে:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

প্রবলেম ১: Maximum Depth of Binary Tree (LeetCode 104)

প্রশ্ন: একটি binary tree-র সর্বোচ্চ গভীরতা (depth/height) বের করুন — root থেকে সবচেয়ে দূরের leaf পর্যন্ত node সংখ্যা।

চিন্তার ধাপ: Tree প্রবলেমের মূল মন্ত্র — "আমার depth = আমার সন্তানদের মধ্যে যার depth বেশি, তার সাথে ১ যোগ।" পুরো tree নিয়ে ভাববেন না, শুধু একটি node আর তার দুই subtree নিয়ে ভাবুন। Recursion বাকিটা সামলে নেবে।

সমাধান:

public int maxDepth(TreeNode root) {
    if (root == null) return 0;  // base case: খালি tree-র depth 0

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

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

Complexity: Time O(n) — প্রতিটি node একবার visit হয়। Space O(h) — recursion stack, h = tree-র height। Worst case (skewed tree) O(n), balanced tree-তে O(log n)।

ইন্টারভিউ টিপ: Space complexity জিজ্ঞেস করলে recursion stack-এর কথা বলতে ভুলবেন না — অনেকে "O(1) extra space" বলে ভুল করে।

প্রবলেম ২: Invert Binary Tree (LeetCode 226)

প্রশ্ন: Tree-টিকে mirror করুন — প্রতিটি node-এর left ও right child অদলবদল করুন।

চিন্তার ধাপ: প্রতিটি node-এ গিয়ে left আর right swap করুন, তারপর দুই subtree-তে একই কাজ recursively করুন। ব্যস।

সমাধান:

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    // left ও right swap
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    // দুই subtree-তে recursive call
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

Complexity: Time O(n), Space O(h)।

মজার তথ্য: এই প্রবলেমটি বিখ্যাত কারণ Homebrew-এর স্রষ্টা Max Howell এটি সমাধান করতে না পারায় Google-এ reject হয়েছিলেন। ইন্টারভিউতে এটি খুবই common।

প্রবলেম ৩: Same Tree (LeetCode 100)

প্রশ্ন: দুটি binary tree সম্পূর্ণ একই কিনা (structure ও value দুটোই) চেক করুন।

চিন্তার ধাপ: দুটি tree একই হবে যদি — (১) দুটোই null হয়, (২) দুটোর root value সমান হয় এবং (৩) তাদের left subtree পরস্পর same হয় এবং right subtree পরস্পর same হয়। এই তিনটি শর্তই কোডে সরাসরি লিখে ফেলুন।

সমাধান:

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;   // দুটোই খালি
    if (p == null || q == null) return false;  // একটি খালি, অন্যটি নয়
    if (p.val != q.val) return false;          // value মেলেনি

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Complexity: Time O(n), Space O(h)।

ইন্টারভিউ টিপ: এই প্যাটার্নটি শিখলে "Symmetric Tree" (LeetCode 101) প্রায় ফ্রি — সেখানে শুধু isSameTree(p.left, q.right) && isSameTree(p.right, q.left) — নিজের mirror-এর সাথে তুলনা।

প্রবলেম ৪: Level Order Traversal / BFS (LeetCode 102)

প্রশ্ন: Tree-টিকে level অনুযায়ী traverse করুন — প্রতিটি level-এর node গুলো আলাদা list-এ রিটার্ন করুন।

চিন্তার ধাপ: এটিই একমাত্র প্রবলেম যেখানে recursion নয়, Queue ব্যবহার করা স্বাভাবিক। মূল কৌশল: loop-এর শুরুতে queue.size() নিয়ে নিন — ওটাই বর্তমান level-এর node সংখ্যা। ঠিক ততগুলো node process করুন, তাদের সন্তানদের queue-তে যোগ করুন।

সমাধান:

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();  // এই মুহূর্তে queue-তে যা আছে, সবই এক level-এর
        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;
}

Complexity: Time O(n), Space O(w) — w = tree-র সর্বোচ্চ প্রস্থ (widest level), worst case O(n)।

ইন্টারভিউ টিপ: levelSize snapshot নেওয়াটাই এই প্যাটার্নের প্রাণ। এটা শিখলে Zigzag Traversal, Right Side View, Minimum Depth — সব একই টেমপ্লেটে সমাধান হয়।

প্রবলেম ৫: Validate Binary Search Tree (LeetCode 98)

প্রশ্ন: একটি tree বৈধ BST কিনা যাচাই করুন — প্রতিটি node-এর left subtree-র সব value তার চেয়ে ছোট, right subtree-র সব value বড় হতে হবে।

চিন্তার ধাপ: সবচেয়ে common ভুল — শুধু node.left.val < node.val < node.right.val চেক করা। এটা যথেষ্ট নয়! কারণ left subtree-র গভীরের কোনো node-ও root-এর চেয়ে বড় হয়ে যেতে পারে। সঠিক পদ্ধতি: প্রতিটি node-এর জন্য একটি বৈধ range (min, max) বহন করা। Left-এ গেলে max কমে যায়, right-এ গেলে min বেড়ে যায়।

সমাধান:

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;

    if (min != null && node.val <= min) return false;
    if (max != null && node.val >= max) return false;

    return validate(node.left, min, node.val)    // left: max হয়ে গেল node.val
        && validate(node.right, node.val, max);  // right: min হয়ে গেল node.val
}

Complexity: Time O(n), Space O(h)।

ইন্টারভিউ টিপ: Integer (null-able) ব্যবহার করা হয়েছে যাতে Integer.MIN_VALUE/MAX_VALUE edge case-এ না আটকায় — interviewer এই edge case টি প্রায়ই জিজ্ঞেস করেন ("node-এর value যদি Integer.MIN_VALUE হয়?")। বিকল্প সমাধান: in-order traversal করলে BST-তে value গুলো sorted আসবে — আগের value-র চেয়ে ছোট বা সমান কিছু পেলেই false।

মূল প্যাটার্ন — মনে রাখুন

১. Tree মানেই recursion: base case (null হলে কী?) + এক node-এর কাজ + subtree-তে বিশ্বাস রাখুন। ২. Level অনুযায়ী কিছু চাইলেই BFS + Queue + levelSize snapshot। ৩. BST প্রবলেমে range/bound বহন করুন, শুধু parent-child তুলনা নয়। ৪. Time প্রায় সবসময় O(n), Space হলো recursion stack O(h) — এটা বলতে ভুলবেন না।

পরবর্তী ধাপ: এই ৫টি আয়ত্তে এলে medium level-এ যান — Lowest Common Ancestor (236), Diameter of Binary Tree (543), Kth Smallest in BST (230)।

Share