Problem link ও উৎস
- **Original source:** Classic binary tree comparison exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Easy
- **Pattern:** Pair recursion
- **Basic idea inherited from:** Subtree comparison pattern — একটা tree-র বদলে দুটো tree একসাথে নামিয়ে মেলানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে দুটো binary tree-র root দেওয়া আছে (`p` আর `q`)। তোমার কাজ: বলো ওরা **হুবহু একরকম** কিনা — মানে একই shape (structure) আর প্রতিটা মিলে যাওয়া জায়গায় একই value। দুটো শর্তই মানতে হবে।
```text
p: 1 q: 1
/ \ / \
2 3 2 3 → same? হ্যাঁ (True)
p: 1 q: 1
/ \
2 2 → same? না (False) — shape আলাদা
```
### Input ও output {#8-example-input-and-output}
```text
Input : p = [1,2,3], q = [1,2,3] -> Output: True
Input : p = [1,2], q = [1,null,2] -> Output: False (shape আলাদা)
Input : p = [1,2,1], q = [1,1,2] -> Output: False (value আলাদা)
Input : p = [], q = [] -> Output: True (দুটোই খালি)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুটো বাড়ির blueprint পাশাপাশি রেখে মেলানোর কথা ভাবো। তুমি একই ঘর ধরে ধরে দুটোতে এগোও: দরজা একই জায়গায়? জানালার সংখ্যা এক? যেই প্রথম একটা অমিল পাও — একটাতে ঘর আছে, অন্যটাতে নেই, বা মাপ আলাদা — তখনই বলে দাও "এক না।" সব ঘর মিলে গেলে তবেই "হুবহু এক।"
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **subtree comparison pattern**-এর প্রথম রূপ (traversal-patterns.md-র Pattern B)। আগের recursion-গুলো একটা tree নামাত; এখানে আমরা **দুটো tree একসাথে, পা মিলিয়ে** নামাই — `p` আর `q`-কে একই step-এ এগোই, প্রতিটা মিল-জায়গায় তুলনা করি। এই "জোড়ায় recursion" idea Symmetric Tree (#7) আর Subtree (#20)-এর ভিত্তি।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো একটা **recursive equality**:
```text
same(empty, empty) = True
same(empty, node) = False (একটা আছে, একটা নেই → shape আলাদা)
same(node, empty) = False
same(a, b) = (a.val == b.val)
and same(a.left, b.left)
and same(a.right, b.right)
```
মানে দুই tree তখনই সমান যখন তাদের root সমান **এবং** বাঁ-subtree জোড়া সমান **এবং** ডান-subtree জোড়া সমান। `and` থাকায় যেকোনো এক জায়গায় মিল না হলেই পুরোটা False।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না। শুধু **recursion call stack** — দুটো tree একসাথে ঘোরানো হয়, প্রতিটা মিল-অবস্থানে এক জোড়া node তুলনা হয়। tree দুটোই নিজেদের data structure।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Tree self-similar (concept.md দেখো), তাই একটা recursive function দুই tree-র মিল-জায়গা সমান্তরালে সামলাতে পারে: root জোড়া মেলাও, তারপর নিজেকে (left, left) আর (right, right) জোড়ায় ডাকো। call stack দুই tree-তে একই path মনে রাখে, তাই pointer দুটো সবসময় মিল-অবস্থানে থাকে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: দুই tree-কে আলাদা করে কোনো traversal (যেমন preorder, None marker সহ) দিয়ে list বানাই, তারপর দুই list সমান কিনা মেলাই।
```text
1) p-র preorder (None সহ): [1, 2, None, None, 3, None, None]
2) q-র preorder (None সহ): [1, 2, None, None, 3, None, None]
3) দুই list মিলে গেলে → True
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই serialize-and-compare ঠিক কাজ করে, কিন্তু **দুই পুরো list আগে বানাতে হয়** — extra O(n) memory, আর tree দুটো প্রথম node-এই আলাদা হলেও পুরোটা serialize করে ফেলে। জোড়ায়-recursion এর চেয়ে ভালো: প্রথম অমিল পেলেই `and` সঙ্গে সঙ্গে থেমে False ফেরায় (short-circuit), কোনো list জমানো ছাড়াই।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **দুই tree একসাথে, একই গতিতে নামালে** প্রতিটা মিল-অবস্থানে শুধু এক জোড়া node তুলনা করলেই চলে। আর None-এর হিসাবটাই আসলে shape মেলায়: এক পাশে node, অন্য পাশে None পাওয়া মানেই structure আলাদা — সঙ্গে সঙ্গে False।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
জোড়ায় recursion: প্রথমে None-গুলো সামলাও (দুটোই None → True; একটা None → False), তারপর value মেলাও, তারপর `and` দিয়ে left-জোড়া আর right-জোড়ায় নামো। `and` থাকায় প্রথম মিথ্যেতেই বাকিটা না দেখে থেমে যায় — দ্রুত exit।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** এক tree-র recursion থেকে দুই tree-র recursion-এ লাফ দাও — function-টা এক node না, **এক জোড়া node** নেয়। তারপর সবচেয়ে কঠিন অংশটা মনে রাখো: structure মেলানোর আসল চাবি হলো None-গুলোর তুলনা। "একটা node, একটা None" দেখলেই থেমে যাও — value মেলানোর দরকারই নেই।
### ছবিতে বোঝা {#7-visual-explanation}
দুই tree-তে একই অবস্থান একসাথে তুলনা হয় (↕ মানে এই জোড়া এখন মেলানো হচ্ছে):
```text
p q
1 ↕ 1 ← 1 == 1, আরও গভীরে নামে
/ \ / \
2 ↕ 2 2 2 ← 2 == 2
\ \
∅ ↕ ∅ ← দুজনেরই left None: ঠিক আছে
কোথাও একটা node, অন্যটা None হলে → সঙ্গে সঙ্গে False
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `p = [1,2]`, `q = [1,null,2]` (p: root 1 left 2; q: root 1 right 2):
1. `same(p=1, q=1)`: দুটোই node, 1 == 1 → এখন left-জোড়া আর right-জোড়া দেখো।
2. বাঁ-জোড়া: `same(p.left = 2, q.left = None)` → একটা node, একটা None → **False**।
3. `and`-এর প্রথম অংশই False হওয়ায় right-জোড়া আর দেখা হয় না।
4. পুরো ফলাফল → **False** (shape আলাদা)।
## কোড ও ব্যাখ্যা {#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_same_tree(p, q):
if p is None and q is None: # দুটোই খালি: এই অবস্থানে মিল
return True
if p is None or q is None: # একটা আছে, একটা নেই: shape আলাদা
return False
if p.val != q.val: # value অমিল
return False
return (is_same_tree(p.left, q.left) # বাঁ-জোড়া
and is_same_tree(p.right, q.right)) # ও ডান-জোড়া, দুটোই মিলতে হবে
# ---- tests ----
assert is_same_tree(build_tree([1, 2, 3]), build_tree([1, 2, 3])) is True
assert is_same_tree(build_tree([1, 2]), build_tree([1, None, 2])) is False # shape আলাদা
assert is_same_tree(build_tree([1, 2, 1]), build_tree([1, 1, 2])) is False # value আলাদা
assert is_same_tree(build_tree([]), build_tree([])) is True # দুটোই খালি
assert is_same_tree(build_tree([1]), build_tree([])) is False # একটা খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if p is None and q is None: return True` — base case; দুই subtree একসাথে শেষ মানে এ পর্যন্ত মিল।
- `if p is None or q is None: return False` — একটা শেষ, অন্যটা নয় → structure আলাদা, সঙ্গে সঙ্গে না।
- `if p.val != q.val: return False` — দুজনেই আছে কিন্তু value আলাদা → না।
- `return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)` — মূল চাল: বাঁ-জোড়া ও ডান-জোড়া দুটোই সমান হতে হবে; `and` প্রথম মিথ্যেতে থেমে যায়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,2,3]` বনাম `[1,2,3]` → True (সব মিলে যায়)। `[1,2]` বনাম `[1,null,2]` → False (dry run-এর সাথে মেলে, shape আলাদা)। `[1,2,1]` বনাম `[1,1,2]` → False (value আলাদা)। দুই খালি → True; একটা খালি → False। সব assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — n হলো ছোট tree-র node সংখ্যা; worst case-এ প্রতিটা মিল-অবস্থানে এক জোড়া node তুলনা হয়। অমিল আগে এলে আরও কম (short-circuit)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(h)** — recursion call stack tree-র height h সমান গভীর হয়। balanced-এ O(log n), chain-এ O(n)। (concept.md-র table দেখো।) আলাদা data structure বানাই না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- দুই None-কে সমান ধরতে ভুলে যাওয়া (base case বাদ) → শেষে `None.val` ছুঁয়ে AttributeError।
- শুধু value মেলানো, কিন্তু "একটা node একটা None" case সামলানো না → ভুলভাবে True।
- `and`-এর বদলে `or` লেখা → শুধু এক দিক মিললেই True হয়ে যায়, ভুল।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: traversal-patterns.md-র Pattern B (subtree comparison) আর concept.md-র recursion। এক-tree recursion বুঝলে দুই-tree জোড়ায় recursion শুধু function-এ একটা বাড়তি argument যোগ করার ব্যাপার।
### পরের অনুশীলন {#22-similar-harder-problems}
- Symmetric Tree (একই জোড়া-recursion, কিন্তু পাশগুলো mirror করে) —