Problem link ও উৎস
- **Original source:** Classic binary tree symmetry exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Easy
- **Pattern:** Pair recursion (mirrored)
- **Basic idea inherited from:** Same Tree, পাশগুলো cross করে — দুই tree না, এক tree-র দুই পাশকে আয়না-জোড়ায় মেলানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: বলো tree-টা তার **কেন্দ্রের চারপাশে আয়নার মতো প্রতিসম (symmetric)** কিনা — মানে বাঁ-অর্ধেক আর ডান-অর্ধেক একে অপরের আয়না-প্রতিচ্ছবি।
```text
1 1
/ \ / \
2 2 2 2
/ \ / \ / \
3 4 4 3 → হ্যাঁ 3 3 → না (mirror না)
```
### Input ও output {#8-example-input-and-output}
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা প্রজাপতির ডানার কথা ভাবো। কেন্দ্রের ভাঁজ বরাবর বাঁ ডানা আর ডান ডানা একে অপরের আয়না — বাঁ ডানার ভেতরের প্রান্ত মেলে ডান ডানার ভেতরের প্রান্তের সাথে, বাঁয়ের বাইরের প্রান্ত মেলে ডানের বাইরের প্রান্তের সাথে। ঠিক উল্টো করে মেলানো — সেটাই symmetry।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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` = ডান পাশ) নেয়:
```text
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/](../../04-stack-and-queue/README.md)), জোড়া জোড়া enqueue করে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Tree self-similar (concept.md দেখো), তাই এক recursive function দুই পাশ আয়না-জোড়ায় সামলাতে পারে: এক জোড়া root মেলাও, তারপর cross করে নিজেকে দুই নতুন জোড়ায় ডাকো। call stack দুই পাশে symmetric path মনে রাখে, তাই pointer দুটো সবসময় mirror-অবস্থানে থাকে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: tree-র বাঁ-subtree-কে আয়নায় উল্টে (invert, #5) ফেলি, তারপর সেই উল্টানো বাঁ-subtree আর আসল ডান-subtree "Same Tree" কিনা মেলাই।
```text
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 নিয়ে না।
### ছবিতে বোঝা {#7-visual-explanation}
বাঁ-subtree (L) আর ডান-subtree (R) cross করে মেলানো হয় (↔ মানে এই জোড়া আয়না-তুলনায়):
```text
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
```
### ছোট input-এ ধাপে ধাপে {#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 না)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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)` — দুই পাশ দিয়ে শুরু।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
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`, তাই দুই খালি পাশ ঠিকঠাক ধরা পড়ে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
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 দেয়।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 বা ভুল উত্তর।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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 ছাড়া, সরাসরি জোড়া মেলানো) —