007 — Symmetric Tree

Source

• Original source: Classic binary tree symmetry exercise
• Platform: LeetCode — https://leetcode.com/problems/symmetric-tree/
• Topic: trees
• Difficulty: Easy
• Pattern: Pair recursion (mirrored)
• Basic idea inherited from: Same Tree, পাশগুলো cross করে — দুই tree না, এক tree-র দুই পাশকে আয়না-জোড়ায় মেলানো

1. Problem in simple words

তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: বলো tree-টা তার কেন্দ্রের চারপাশে আয়নার মতো প্রতিসম (symmetric) কিনা — মানে বাঁ-অর্ধেক আর ডান-অর্ধেক একে অপরের আয়না-প্রতিচ্ছবি।

    1                    1
   / \                  / \
  2   2                2   2
 / \ / \              /     \
3  4 4  3   → হ্যাঁ   3       3   → না (mirror না)

2. Which basic idea does this inherit from?

এটা সরাসরি Same Tree (#6) থেকে আসে — একই জোড়ায়-recursion, কিন্তু একটা ছোট মোচড় সহ। Same Tree-তে আমরা (left, left) আর (right, right) মেলাতাম। এখানে এক tree-র দুই পাশকে আয়না হিসেবে মেলাতে পাশগুলো cross করি: এক পাশের left মেলে অন্য পাশের right-এর সাথে। Same Tree-র "mirrored" সংস্করণ।

3. What is the hidden math or logic?

লুকানো logic একটা mirror-equality যা এক জোড়া node (a = বাঁ পাশ, b = ডান পাশ) নেয়:

mirror(empty, empty) = True
mirror(empty, node)  = False
mirror(node,  empty) = False
mirror(a, b) = (a.val == b.val)
               and mirror(a.left,  b.right)   ← cross!
               and mirror(a.right, b.left)    ← cross!

মূল চাল ওই cross: a-র বাঁ তুলনা হয় b-র ডান-এর সাথে আর উল্টোটা। tree symmetric তখনই যখন root-এর left-subtree আর right-subtree এভাবে mirror করে মেলে।

4. Which data structure is needed?

কোনো extra data structure লাগে না। শুধু recursion call stack — এক জোড়া node (বাঁ পাশ ও ডান পাশ) একসাথে নামানো হয়। চাইলে একটা queue দিয়ে iterative-ও করা যায় (../../04-stack-and-queue/), জোড়া জোড়া enqueue করে।

5. Why this data structure fits

Tree self-similar (concept.md দেখো), তাই এক recursive function দুই পাশ আয়না-জোড়ায় সামলাতে পারে: এক জোড়া root মেলাও, তারপর cross করে নিজেকে দুই নতুন জোড়ায় ডাকো। call stack দুই পাশে symmetric path মনে রাখে, তাই pointer দুটো সবসময় mirror-অবস্থানে থাকে।

6. Real-life analogy

একটা প্রজাপতির ডানার কথা ভাবো। কেন্দ্রের ভাঁজ বরাবর বাঁ ডানা আর ডান ডানা একে অপরের আয়না — বাঁ ডানার ভেতরের প্রান্ত মেলে ডান ডানার ভেতরের প্রান্তের সাথে, বাঁয়ের বাইরের প্রান্ত মেলে ডানের বাইরের প্রান্তের সাথে। ঠিক উল্টো করে মেলানো — সেটাই symmetry।

7. Visual explanation

বাঁ-subtree (L) আর ডান-subtree (R) cross করে মেলানো হয় (↔ মানে এই জোড়া আয়না-তুলনায়):

        1
       / \
      L   R
   2 ↔ 2            ← L.root == R.root
  / \   / \
 3   4 4   3
 ↑   ↑ ↑   ↑
 L.left ↔ R.right   (3 ↔ 3)
 L.right ↔ R.left   (4 ↔ 4)   ← cross করে মেলে → symmetric

8. Example input and output

Input : root = [1,2,2,3,4,4,3]      -> Output: True
Input : root = [1,2,2,null,3,null,3] -> Output: False  (mirror না)
Input : root = []                    -> Output: True   (খালি tree symmetric ধরা হয়)
Input : root = [1]                   -> Output: True   (একটা node)

9. Brute force thinking

প্রথম সরল চিন্তা: tree-র বাঁ-subtree-কে আয়নায় উল্টে (invert, #5) ফেলি, তারপর সেই উল্টানো বাঁ-subtree আর আসল ডান-subtree "Same Tree" কিনা মেলাই।

1) left subtree-র একটা mirrored কপি বানাও
2) সেই কপি আর right subtree Same Tree কিনা দেখো
3) মিলে গেলে → tree symmetric

10. Why brute force is slow

এই invert-then-compare ঠিক কাজ করে, কিন্তু একটা পুরো subtree-র mirrored কপি আগে বানাতে হয় — extra O(n) memory আর কাজ। জোড়ায়-mirror-recursion সেটা এড়ায়: কোনো কপি না বানিয়েই, নামার সময়েই cross করে তুলনা করে, আর প্রথম অমিলে and থেমে যায়।

11. Key observation

মূল observation: symmetry মানে root-এর দুই পাশ একে অপরের আয়না। আর আয়না-তুলনার চাবি ওই cross: এক পাশের বাইরের প্রান্ত (left.left) মেলে অন্য পাশের বাইরের প্রান্ত (right.right)-এর সাথে, ভেতরের সাথে ভেতরের। এই cross-pairing ঠিকভাবে করলেই পুরো mirror-চেক হয়ে যায়।

12. Optimized intuition

একটা helper mirror(a, b) বানাও — a বাঁ পাশ, b ডান পাশ। আগে None-cases (দুটোই None → True, একটা None → False), তারপর value মেলাও, তারপর cross করে and দিয়ে দুই জোড়ায় নামো: (a.left, b.right) আর (a.right, b.left)। root থেকে শুরু করো mirror(root.left, root.right) দিয়ে।

13. Thinking tweak

মোচড়: Same Tree-র জোড়া-recursion-টা নাও, তারপর শুধু ভেতরের দুই recursive call-এ left আর right cross করে দাও। ওই এক অদলবদলেই "দুটো একরকম?" প্রশ্ন "একটা কি অন্যটার আয়না?" প্রশ্নে বদলে যায়। আর গোড়াতেই tree-টাকে দুই ভাগে ভাঙো: root.left আর root.right দিয়ে শুরু করো, পুরো root নিয়ে না।

14. Step-by-step dry run

Input [1,2,2,null,3,null,3] (root 1; left 2 যার right 3; right 2 যার right 3):

1. mirror(root.left = 2, root.right = 2): দুটোই node, 2 == 2 → cross করে নামো।
2. বাইরের জোড়া: mirror(a.left = None, b.right = 3) → একটা None, একটা node → False।
3. and-এর প্রথম অংশ False হওয়ায় ভেতরের জোড়া আর দেখা হয় না।
4. পুরো ফলাফল → False (mirror না)।

15. Python solution

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(values):
    """level-order list (None = missing child) থেকে tree বানায়।"""
    if not values:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


def is_symmetric(root):
    def mirror(a, b):
        if a is None and b is None:     # দুই পাশই খালি: মিল
            return True
        if a is None or b is None:      # একটা আছে, একটা নেই: mirror ভাঙল
            return False
        if a.val != b.val:              # value অমিল
            return False
        return (mirror(a.left, b.right)     # বাইরের জোড়া (cross)
                and mirror(a.right, b.left))  # ভেতরের জোড়া (cross)

    if root is None:                    # খালি tree symmetric ধরা হয়
        return True
    return mirror(root.left, root.right)


# ---- tests ----
assert is_symmetric(build_tree([1, 2, 2, 3, 4, 4, 3])) is True
assert is_symmetric(build_tree([1, 2, 2, None, 3, None, 3])) is False  # mirror না
assert is_symmetric(build_tree([])) is True                            # খালি tree
assert is_symmetric(build_tree([1])) is True                           # একটা node
assert is_symmetric(build_tree([1, 2, 2, 2, None, 2])) is False        # value/shape অমিল
print("সব test pass!")

16. Line-by-line code explanation

• def mirror(a, b) — ভেতরের helper; a বাঁ পাশ, b ডান পাশ, আয়না-জোড়া মেলায়।
• if a is None and b is None: return True — দুই পাশ একসাথে শেষ → এ পর্যন্ত mirror ঠিক।
• if a is None or b is None: return False — একটা শেষ, অন্যটা নয় → mirror ভেঙে গেল।
• if a.val != b.val: return False — দুজনেই আছে কিন্তু value আলাদা → না।
• return mirror(a.left, b.right) and mirror(a.right, b.left) — মূল চাল: cross-pairing — a-র বাঁ মেলে b-র ডান, a-র ডান মেলে b-র বাঁ।
• if root is None: return True — খালি tree-কে symmetric ধরা হয়।
• return mirror(root.left, root.right) — দুই পাশ দিয়ে শুরু।

17. Output walkthrough

[1,2,2,3,4,4,3] → True (cross করে সব মেলে)। [1,2,2,null,3,null,3] → False (dry run-এর সাথে মেলে)। খালি → True; একক node → True; [1,2,2,2,null,2] → False (এক পাশে node, অন্য পাশে None)। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(n) — worst case-এ প্রতিটা node ঠিক একবার এক mirror-জোড়ার অংশ হিসেবে দেখা হয়। অমিল আগে এলে আরও কম (short-circuit)।

19. Space complexity

O(h) — recursion call stack tree-র height h সমান গভীর হয়। balanced-এ O(log n), chain-এ O(n)। (concept.md-র table দেখো।)

20. Common mistakes

• cross করতে ভুলে গিয়ে mirror(a.left, b.left) লেখা → সেটা Same Tree, symmetry না।
• root-কে নিজের সাথে মেলানো (mirror(root, root)) → সবসময় True, ভুল; root.left আর root.right দিয়ে শুরু করতে হয়।
• "একটা node একটা None" case সামলানো না → AttributeError বা ভুল উত্তর।

21. Which basic problem this inherits from

ভিত্তি: Same Tree (#6)-র pair recursion। সেই কঙ্কালটাই এখানে — শুধু ভেতরের দুই call-এ left/right cross করা হয়েছে। concept.md-র recursion আর self-similarity তো base হিসেবে আছেই।

22. Similar harder problems

• Same Tree (cross ছাড়া, সরাসরি জোড়া মেলানো) — https://leetcode.com/problems/same-tree/ (এই tracker-এর #6)
• Invert Binary Tree (পুরো tree আয়নায় উল্টানো) — https://leetcode.com/problems/invert-binary-tree/ (#5)
• Flip Equivalent Binary Trees (কিছু child swap করে দুই tree মেলানো যায় কিনা) — https://leetcode.com/problems/flip-equivalent-binary-trees/

23. Pattern learned

Mirrored pair recursion: Same Tree-র জোড়া-recursion নাও, ভেতরের call-এ left ও right cross করে দাও — পেলে আয়না-চেক। symmetry-জাতীয় যেকোনো প্রশ্নের signature চাল।

24. Final summary

ভবিষ্যতের আমাকে: "Symmetric = Same Tree, কিন্তু ভেতরের call-এ left↔right cross; শুরু করো root.left ও root.right দিয়ে।" আয়না/mirror/প্রতিসম শব্দ শুনলেই এই cross-pairing মনে পড়বে। মূল চাবি: এক পাশের বাইরের প্রান্ত মেলে অন্য পাশের বাইরের প্রান্তের সাথে।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function buildTree(values) {
  if (!values || values.length === 0) return null;
  const root = new TreeNode(values[0]);
  const q = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const node = q[head++];
    if (i < values.length && values[i] !== null) { node.left = new TreeNode(values[i]); q.push(node.left); }
    i++;
    if (i < values.length && values[i] !== null) { node.right = new TreeNode(values[i]); q.push(node.right); }
    i++;
  }
  return root;
}

function isSymmetric(root) {
  const mirror = (a, b) => {
    if (a === null && b === null) return true;   // দুই পাশই খালি: মিল
    if (a === null || b === null) return false;  // একটা আছে, একটা নেই: mirror ভাঙল
    if (a.val !== b.val) return false;           // value অমিল
    return mirror(a.left, b.right)               // বাইরের জোড়া (cross)
        && mirror(a.right, b.left);              // ভেতরের জোড়া (cross)
  };
  if (root === null) return true;                // খালি tree symmetric ধরা হয়
  return mirror(root.left, root.right);
}

// ---- test cases ----
assert(isSymmetric(buildTree([1, 2, 2, 3, 4, 4, 3])) === true, "symmetric");
assert(isSymmetric(buildTree([1, 2, 2, null, 3, null, 3])) === false, "mirror না");
assert(isSymmetric(buildTree([])) === true, "খালি tree");
assert(isSymmetric(buildTree([1])) === true, "একটা node");
assert(isSymmetric(buildTree([1, 2, 2, 2, null, 2])) === false, "shape অমিল");
console.log("সব JS test pass!");

JS টীকা: এখানে return value boolean, তাই array-equality ঝামেলা নেই — সরাসরি === true/=== false দিয়ে assert করা যায়। JS-এর && Python-এর and-এর মতোই short-circuit করে: প্রথম mirror(...) false হলে দ্বিতীয়টা ডাকাই হয় না, তাই অমিল আগে এলে কাজ কম। null === null JS-এ true, তাই দুই খালি পাশ ঠিকঠাক ধরা পড়ে।

26. TypeScript solution (with test cases)

interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }

function node(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
  return { val, left, right };
}

function buildTree(values: (number | null)[]): TreeNode | null {
  if (values.length === 0) return null;
  const root = node(values[0] as number);
  const q: TreeNode[] = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const cur = q[head++];
    if (i < values.length && values[i] !== null) { cur.left = node(values[i] as number); q.push(cur.left); }
    i++;
    if (i < values.length && values[i] !== null) { cur.right = node(values[i] as number); q.push(cur.right); }
    i++;
  }
  return root;
}

function isSymmetric(root: TreeNode | null): boolean {
  const mirror = (a: TreeNode | null, b: TreeNode | null): boolean => {
    if (a === null && b === null) return true;
    if (a === null || b === null) return false;
    if (a.val !== b.val) return false;
    return mirror(a.left, b.right) && mirror(a.right, b.left);
  };
  if (root === null) return true;
  return mirror(root.left, root.right);
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };

expect(isSymmetric(buildTree([1, 2, 2, 3, 4, 4, 3])) === true, "sym");
expect(isSymmetric(buildTree([1, 2, 2, null, 3, null, 3])) === false, "না");
expect(isSymmetric(buildTree([])) === true, "খালি");
expect(isSymmetric(buildTree([1])) === true, "একক");
expect(isSymmetric(buildTree([1, 2, 2, 2, null, 2])) === false, "shape");
console.log("সব TS test pass!");

TS টীকা: mirror-এর প্যারামিটার দুটো TreeNode | null হওয়ায় compiler বাধ্য করে — a.val বা a.left ছোঁয়ার আগে আমরা null cases আগে handle করি (narrowing)। তাই "একটা node একটা null" case ভুলে গেলে compile-time-এই ধরা পড়ে, runtime-এ undefined-এর crash নয়। boolean return type কোথাও ভুলে value/undefined ফেরত দিলে error দেয়।

27. কোথায় কাজে লাগে (real-world use)

• UI layout validation: একটা symmetric design (যেমন split-screen বা মিরর করা navigation) সত্যিই দুই পাশে আয়না-প্রতিসম কিনা automated test-এ যাচাই করা।
• Image symmetry detection: ছবি বা pattern-এর বাঁ-ডান প্রতিসমতা পরীক্ষা — চেহারা শনাক্তকরণ বা quality control-এ একটা feature।
• Molecular / structural symmetry: রসায়ন বা CAD-এ একটা গঠন তার অক্ষ বরাবর প্রতিসম কিনা পরীক্ষা করা (tree-আকারে modeled হলে)।
• Game board fairness: দুই-খেলোয়াড়ের খেলায় starting position দুই পাশে সমান (mirror) কিনা যাচাই করা।
• Data integrity / palindrome-style checks: কোনো hierarchical config-এর দুই অর্ধ একে অপরের প্রতিচ্ছবি হওয়ার কথা থাকলে সেটা নিশ্চিত করা।

মূল সুর: "এই দুই অর্ধ কি একে অপরের আয়না?" — এই প্রশ্ন উঠলেই cross-paired pair recursion-এর কথা ভাববে।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।