ভূমিকা

Binary Tree হলো সবচেয়ে গুরুত্বপূর্ণ data structure যা প্রায় প্রতিটি কোডিং ইন্টারভিউতে আসে। এই পোস্টে ৫টি Easy স্তরের Tree সমস্যা Java সমাধান ও বাংলা ব্যাখ্যা সহ দেওয়া হয়েছে।

Binary Tree — মূল ধারণা

// TreeNode definition (সব সমস্যায় ব্যবহৃত)
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

Tree Traversal-এর ধরন:

• Inorder: বাম → Root → ডান (BST-এ sorted order দেয়)
• Preorder: Root → বাম → ডান (tree copy করতে কাজে লাগে)
• Postorder: বাম → ডান → Root (tree delete করতে কাজে লাগে)
• Level Order (BFS): Level by level উপর থেকে নিচে

---

সমস্যা ১: Binary Tree-র Inorder Traversal

সমস্যা: একটি Binary Tree-র Inorder traversal করুন এবং node-এর মানগুলো list-এ রিটার্ন করুন।

উদাহরণ:

Input:
    1
     \
      2
     /
    3

Output: [1, 3, 2]
(বাম → Root → ডান)

চিন্তার ধাপ:

• Inorder = বাম subtree → current node → ডান subtree
• Recursive অথবা Iterative Stack দিয়ে সমাধান করা যায়
• BST-এর Inorder traversal সবসময় sorted order দেয়

Java সমাধান:

import java.util.*;

class Solution {

    // পদ্ধতি ১: Recursive (সহজ ও সংক্ষিপ্ত)
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;      // Base case
        inorder(node.left, result);    // বাম subtree আগে
        result.add(node.val);          // Root যোগ করো
        inorder(node.right, result);   // ডান subtree শেষে
    }

    // পদ্ধতি ২: Iterative Stack দিয়ে
    public List<Integer> inorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // সবচেয়ে বাম node পর্যন্ত যাও
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // Stack থেকে node বের করো
            current = stack.pop();
            result.add(current.val);   // Process করো
            current = current.right;   // ডানে যাও
        }
        return result;
    }
}

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

মূল কৌশল: Recursive পদ্ধতি মনে রাখুন: inorder(left) → process → inorder(right)। Iterative পদ্ধতিতে Stack দিয়ে recursion simulate করা হয়।

---

সমস্যা ২: Invert Binary Tree (Mirror করা)

সমস্যা: একটি Binary Tree-র প্রতিটি node-এর বাম ও ডান child swap করুন (tree-কে mirror করুন)।

উদাহরণ:

Input:          Output:
      4               4
     / \             / \
    2   7    →      7   2
   / \ / \         / \ / \
  1  3 6  9       9  6 3  1

চিন্তার ধাপ:

• প্রতিটি node-এ বাম ও ডান child swap করতে হবে
• এটি recursively করা যায়: প্রথমে বাম ও ডান subtree invert করো, তারপর swap করো
• অথবা BFS দিয়ে level by level swap করা যায়

Java সমাধান:

import java.util.*;

class Solution {

    // পদ্ধতি ১: Recursive DFS
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null; // Base case

        // বাম ও ডান subtree আগে invert করো
        TreeNode leftInverted  = invertTree(root.left);
        TreeNode rightInverted = invertTree(root.right);

        // তারপর swap করো
        root.left  = rightInverted;
        root.right = leftInverted;

        return root;
    }

    // পদ্ধতি ২: Iterative BFS (Queue দিয়ে)
    public TreeNode invertTreeBFS(TreeNode root) {
        if (root == null) return null;

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

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

            // বাম ও ডান swap করো
            TreeNode temp  = node.left;
            node.left      = node.right;
            node.right     = temp;

            // Children Queue-তে যোগ করো
            if (node.left  != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

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

মূল কৌশল: Recursive পদ্ধতি: প্রথমে subtree invert করো, তারপর current node-এ swap করো। এই "bottom-up" চিন্তা অনেক tree সমস্যায় কাজে লাগে।

---

সমস্যা ৩: Path Sum — Root থেকে Leaf পর্যন্ত নির্দিষ্ট যোগফল আছে কিনা

সমস্যা: একটি Binary Tree এবং একটি targetSum দেওয়া আছে। Root থেকে যেকোনো leaf node পর্যন্ত এমন কোনো path আছে কিনা যেখানে সব node-এর মানের যোগফল targetSum-এর সমান?

উদাহরণ:

Target = 22

          5
         / \
        4   8
       /   / \
      11  13   4
     /  \       \
    7    2        1

Output: true
Path: 5 → 4 → 11 → 2 = 22

চিন্তার ধাপ:

• Root থেকে leaf পর্যন্ত যাব, প্রতিটি step-এ remaining sum কমাতে থাকব
• Leaf node-এ পৌঁছে remaining sum == current node value হলে path পাওয়া গেছে
• DFS ব্যবহার করব

Java সমাধান:

import java.util.*;

class Solution {

    // পদ্ধতি ১: Recursive DFS
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        // Leaf node: remaining sum == current value হলে true
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        // Remaining sum কমিয়ে বাম ও ডানে check করো
        int remaining = targetSum - root.val;
        return hasPathSum(root.left, remaining)
            || hasPathSum(root.right, remaining);
    }

    // পদ্ধতি ২: Iterative (Stack দিয়ে, node ও remaining sum একসাথে)
    public boolean hasPathSumIterative(TreeNode root, int targetSum) {
        if (root == null) return false;

        // Stack-এ [node, remaining_sum] জোড়া রাখব
        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer>  sumStack  = new Stack<>();

        nodeStack.push(root);
        sumStack.push(targetSum - root.val);

        while (!nodeStack.isEmpty()) {
            TreeNode node      = nodeStack.pop();
            int      remaining = sumStack.pop();

            // Leaf node: remaining == 0 হলে path পাওয়া গেছে
            if (node.left == null && node.right == null && remaining == 0) {
                return true;
            }

            if (node.right != null) {
                nodeStack.push(node.right);
                sumStack.push(remaining - node.right.val);
            }
            if (node.left != null) {
                nodeStack.push(node.left);
                sumStack.push(remaining - node.left.val);
            }
        }
        return false;
    }
}

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

মূল কৌশল: Leaf node check করুন — left == null && right == null। Remaining sum কমিয়ে নিচে যাওয়া এবং leaf-এ remaining == node.val check করা সবচেয়ে গুরুত্বপূর্ণ।

---

সমস্যা ৪: Binary Search Tree (BST) Validation

সমস্যা: একটি Binary Tree দেওয়া আছে। এটি valid BST কিনা নির্ধারণ করুন।

BST-এর নিয়ম:

• বাম subtree-র সব node < current node
• ডান subtree-র সব node > current node
• বাম ও ডান উভয় subtree-ও valid BST হতে হবে

উদাহরণ:

Valid BST:         Invalid BST:
    2                  5
   / \                / \
  1   3               1   4
                         / \
                        3   6
(4 < 5 হওয়া উচিত কিন্তু 5-এর ডানে আছে — invalid)

চিন্তার ধাপ:

• শুধু immediate parent-এর সাথে compare করলে হবে না
• প্রতিটি node-এর জন্য valid range (min, max) track করতে হবে
• বাম subtree-তে যাওয়ার সময় max = current node value
• ডান subtree-তে যাওয়ার সময় min = current node value

Java সমাধান:

class Solution {

    // পদ্ধতি ১: Min/Max Range দিয়ে (সবচেয়ে efficient)
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true; // null node সবসময় valid

        // Current node-এর value valid range-এ আছে কিনা
        if (node.val <= min || node.val >= max) return false;

        // বাম: max = current value, ডান: min = current value
        return validate(node.left,  min,       node.val)
            && validate(node.right, node.val,  max);
    }

    // পদ্ধতি ২: Inorder Traversal (BST-এর inorder সবসময় sorted)
    public boolean isValidBSTInorder(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        buildInorder(root, inorder);

        // Sorted কিনা check করো
        for (int i = 1; i < inorder.size(); i++) {
            if (inorder.get(i) <= inorder.get(i - 1)) return false;
        }
        return true;
    }

    private void buildInorder(TreeNode node, List<Integer> list) {
        if (node == null) return;
        buildInorder(node.left, list);
        list.add(node.val);
        buildInorder(node.right, list);
    }
}

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

মূল কৌশল: Long.MIN_VALUE এবং Long.MAX_VALUE ব্যবহার করুন (int range overflow এড়াতে)। প্রতিটি node-এ valid range পাস করা — এটি সবচেয়ে elegant solution।

---

সমস্যা ৫: Lowest Common Ancestor (LCA) of Binary Tree

সমস্যা: একটি Binary Tree এবং দুটি node p ও q দেওয়া আছে। তাদের Lowest Common Ancestor (সবচেয়ে নিচের সাধারণ পূর্বপুরুষ) খুঁজুন।

LCA-এর সংজ্ঞা: যে node p ও q উভয়কে তার descendant হিসেবে রাখে, তাদের মধ্যে সবচেয়ে নিচেরটি।

উদাহরণ:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

LCA(5, 1) = 3
LCA(5, 4) = 5   ← 5 নিজেই 4-এর ancestor

চিন্তার ধাপ:

• DFS দিয়ে recursively খুঁজব
• যদি current node == p বা q হয়, সেটাই return করো
• বাম ও ডান থেকে result পাই:
  • উভয় দিক থেকে non-null পেলে current node-ই LCA
  • একদিক থেকে non-null পেলে সেটাই LCA

Java সমাধান:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: null বা p বা q পেলে সেটাই return করো
        if (root == null) return null;
        if (root == p || root == q) return root;

        // বাম ও ডান subtree-তে খোঁজো
        TreeNode leftLCA  = lowestCommonAncestor(root.left,  p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // উভয় দিকে পাওয়া গেছে → current node-ই LCA
        if (leftLCA != null && rightLCA != null) return root;

        // যেদিকে পাওয়া গেছে সেটা return করো
        return leftLCA != null ? leftLCA : rightLCA;
    }
}

উদাহরণ ব্যাখ্যা (LCA(5, 4)):

- root=3: বাম (5-এর subtree) ও ডান (1-এর subtree) explore করো
- root=5: root == p (5), তাই 5 return করো
- root=1: না 4, না 5, বাম ও ডান explore করো → null পাবে
- root=3: leftLCA=5, rightLCA=null → 5 return করো ✓

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

মূল কৌশল: যখন দুটি subtree থেকে দুটি ভিন্ন non-null result আসে, তখন current node-ই LCA। এই "post-order" pattern অনেক tree সমস্যার মূল।

---

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

সমস্যা	Approach	Time	Space	মূল Pattern
Inorder Traversal	DFS Recursive/Stack	O(n)	O(n)	left → node → right
Invert Binary Tree	DFS post-order	O(n)	O(n)	Swap after recursion
Path Sum	DFS + remaining sum	O(n)	O(h)	Leaf check + reduce sum
Validate BST	DFS + min/max range	O(n)	O(h)	Range narrowing
LCA	DFS post-order	O(n)	O(h)	Both sides non-null = LCA

---

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

Tree সমস্যা solve করার চিন্তার কাঠামো:

ধাপ ১ — কোন traversal দরকার?

• Level processing দরকার → BFS (Queue)
• Depth/Path/Subtree কাজ → DFS (Recursive)

ধাপ ২ — কখন কী return করব?

• Base case: if (root == null) return ...
• Leaf case: if (root.left == null && root.right == null) return ...

ধাপ ৩ — Top-down নাকি Bottom-up?

• Top-down (Preorder): তথ্য উপর থেকে নিচে পাস করো (min/max range)
• Bottom-up (Postorder): নিচ থেকে তথ্য উপরে নিয়ে আসো (height, LCA)

// সাধারণ Tree DFS Template
ReturnType solve(TreeNode node, /* extra params */) {
    // 1. Base case
    if (node == null) return baseValue;

    // 2. Recursive calls
    ReturnType left  = solve(node.left,  /* params */);
    ReturnType right = solve(node.right, /* params */);

    // 3. Combine results
    return combine(left, right, node.val);
}