Problem link ও উৎস
- **Original source:** Classic "is this tree contained inside that tree" exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Subtree comparison
- **Basic idea inherited from:** Same Tree (#6), প্রতিটা node-এ প্রয়োগ করা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে দুটো binary tree দেওয়া আছে — একটা বড় `root`, আর একটা ছোট `subRoot`। তোমার কাজ: বলা যে বড় tree-র মধ্যে কোথাও এমন কোনো node আছে কি না, যেখান থেকে শুরু করলে নিচের পুরো subtree-টা হুবহু `subRoot`-এর সমান (একই গঠন, একই value)।
মনে রেখো — "subtree" মানে কোনো একটা node আর তার **নিচের সবকিছু**, মাঝপথে কেটে নেওয়া অংশ নয়। তাই match হতে হলে নিচ পর্যন্ত পুরোটা মিলতে হবে।
```text
3 4 subRoot পুরোটা root-এর বাঁ পাশে বসে আছে
/ \ / \
4 5 1 2 → answer: True
/ \
1 2
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [3,4,5,1,2], subRoot = [4,1,2]
Output: True
Input : root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: False (4-এর নিচে বাড়তি node 0 আছে, হুবহু মেলে না)
Edge : root = [1,1], subRoot = [1] -> Output: True
Edge : root = [1], subRoot = [1] -> Output: True
Edge : root = [1,2], subRoot = [2] -> Output: True
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার হাতে একটা ছোট পরিবার-গাছের ছবি (`subRoot`), আর একটা বিশাল বংশলতিকা (`root`)। তুমি বড় গাছের প্রতিটা মানুষের কাছে গিয়ে জিজ্ঞেস করছ: "তোমাকে শিকড় ধরে নিচের দিকে দেখলে কি ঠিক এই ছোট ছবিটার মতো দেখায়?" কারো ক্ষেত্রে পুরো নিচটা হুবহু মিললেই তুমি বলবে "পেয়েছি"। প্রতিটা ব্যক্তির কাছে প্রশ্ন = outer walk; নিচটা মিলিয়ে দেখা = inner compare।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Same Tree** (#6)-এর উপর দাঁড়ায়। Same Tree বলত "এই দুটো tree কি ঠিক এক?" — এখানে আমরা সেই `is_same` যাচাইটা বড় tree-র **প্রতিটা node-এ** চালাই: "এই node থেকে শুরু করা subtree কি `subRoot`-এর সমান?" একটায় হ্যাঁ পেলেই উত্তর True। মানে একটা inner equality-check + একটা outer "সব node ঘোরা" traversal।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই স্তর — একটা loop-এর ভেতরে আরেকটা যাচাই:
```text
is_subtree(root, sub):
root None হলে → False (খালি tree-তে non-empty sub নেই)
is_same(root, sub) → True হলে সাথে সাথে True
নইলে → is_subtree(root.left, sub) OR is_subtree(root.right, sub)
is_same(a, b):
দুটোই None → True
একটা None → False
val আলাদা → False
নইলে → left মেলে AND right মেলে
```
বাইরের function প্রতিটা node-এ থামে; ভেতরের function সেই node থেকে পুরো গঠন মেলায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — দুটো **recursion**: একটা outer (`is_subtree`, সব candidate node ঘোরে) আর একটা inner (`is_same`, দুটো tree তুলনা করে)। দুই tree নিজেরাই data structure, আর **call stack** কোথায় আছি মনে রাখে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Tree **self-similar** (concept.md দেখো): প্রতিটা node নিজেই একটা পূর্ণ subtree-র root। তাই "প্রতিটা node-কে সম্ভাব্য শুরু ধরে যাচাই করা" recursion দিয়ে নিখুঁত খাপ খায় — outer recursion candidate বাছে, inner recursion লক্ষ্য করে দুটো গঠন একসাথে মেলায়। কোনো index বা পাশের buffer লাগে না, কারণ tree-র আকৃতিই navigation দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: বড় tree-র **প্রতিটা node**-কে সম্ভাব্য শুরু ধরো, আর প্রতিটার জন্য পুরো `is_same` যাচাই চালাও।
```text
1) root-এর সব node তালিকা করো: 3, 4, 5, 1, 2
2) প্রতিটার জন্য is_same(node, subRoot) চালাও
3) কোথাও True পেলে থামো; না পেলে False
```
মজার ব্যাপার — এই "brute force"-টাই এখানে আদর্শ সমাধান, কারণ আমাদের সত্যিই প্রতিটা সম্ভাব্য শুরু দেখতে হয়।
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ভয়ংকর ধীর নয়, তবে worst case-এ একটু খরচালি: প্রতিটা node-এ (`m`টা) inner compare চলতে পারে যা ছোট tree-র আকার (`n`) পর্যন্ত যায়, তাই **O(m·n)**। দুটো tree যদি অনেক একইরকম প্রায়-mil অংশে ভরা থাকে, তবে compare বারবার অনেকদূর গিয়ে শেষে fail করে — সেটাই অপচয়। (string-hashing/Merkle hash দিয়ে গড়ে দ্রুত করা যায়, কিন্তু সেটা পরের ধাপ।)
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **"subtree খোঁজা" = "প্রতিটা node-এ একটা Same-Tree যাচাই চালানো।"** দুটো আলাদা সমস্যা নয় — একটা পরিচিত সমস্যা (Same Tree) আরেকটা traversal-এর ভেতরে বসানো। আর match-টা হতে হবে **নিচ পর্যন্ত পুরো**, মাঝপথে থামলে চলবে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুই recursion আলাদা করে ভাবো। **outer** (`is_subtree`) একটা preorder walk: এই node-এ মেলে কি? না হলে বাঁয়ে বা ডানে খোঁজো (`OR`)। **inner** (`is_same`) একটা lockstep compare: দুটো গঠন একসাথে নামে, এক জায়গায় গরমিল পেলেই False। প্রথম True পেলেই `or`-এর short-circuit বাকিটা থামিয়ে দেয়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** নতুন কিছু আবিষ্কার করতে যেও না। মনে করো "আমার কাছে তো আগে থেকেই Same Tree আছে" — শুধু সেটা প্রতিটা node-এ চালাও। দুটো প্রশ্ন আলাদা রাখো: (১) *এখান থেকে* মেলে কি (`is_same`)? (২) আর *কোথাও* মেলে কি (left/right-এ recurse)? এই দুটো গুলিয়ে ফেললেই bug।
### ছবিতে বোঝা {#7-visual-explanation}
বাইরের walk প্রতিটা node-এ `is_same` চালায়; node 4-এ গিয়ে পুরো গঠন মেলে:
```text
3 is_same(3, sub)? না (4 ≠ 3)
/ \
4 5 is_same(4, sub)? হ্যাঁ ✓ → True
/ \
1 2 (এখানে আর নামার দরকার নেই)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`root = [3,4,5,1,2]`, `subRoot = [4,1,2]`:
1. `is_subtree(3, sub)`: `is_same(3, 4)`? না (3 ≠ 4)। তাই বাঁ/ডানে খোঁজো।
2. `is_subtree(4, sub)`: `is_same(4, 4)`? val মেলে → left: `is_same(1,1)` ✓, right: `is_same(2,2)` ✓ → True।
3. `or`-এর বাঁ দিক True হয়ে গেছে → পুরো উত্তর **True**, ডান (5) আর দেখার দরকার নেই।
## কোড ও ব্যাখ্যা {#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(a, b):
if a is None and b is None: # দুটোই খালি → মেলে
return True
if a is None or b is None: # একটা খালি, একটা না → মেলে না
return False
if a.val != b.val: # value আলাদা → মেলে না
return False
return is_same(a.left, b.left) and is_same(a.right, b.right)
def is_subtree(root, sub):
if root is None: # খালি tree-তে non-empty sub নেই
return False
if is_same(root, sub): # এই node থেকে পুরো গঠন মেলে?
return True
# নইলে বাঁ বা ডান subtree-তে খোঁজো
return is_subtree(root.left, sub) or is_subtree(root.right, sub)
# ---- tests ----
assert is_subtree(build_tree([3, 4, 5, 1, 2]), build_tree([4, 1, 2])) is True
assert is_subtree(
build_tree([3, 4, 5, 1, 2, None, None, None, None, 0]),
build_tree([4, 1, 2]),
) is False
assert is_subtree(build_tree([1, 1]), build_tree([1])) is True
assert is_subtree(build_tree([1]), build_tree([1])) is True
assert is_subtree(build_tree([1, 2]), build_tree([2])) is True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `is_same(a, b)` — Same Tree (#6)-এর হুবহু সেই function: দুই None → True; এক None → False; val আলাদা → False; নইলে left আর right দুটোই মিলতে হবে।
- `if root is None: return False` — outer base case: আর কোনো candidate node নেই, তাই এখানে sub পাওয়া যাবে না।
- `if is_same(root, sub): return True` — এই node-কে শুরু ধরে পুরো গঠন `sub`-এর সমান হলে কাজ শেষ।
- `return is_subtree(root.left, sub) or is_subtree(root.right, sub)` — নইলে বাঁ বা ডান subtree-তে খোঁজো; `or` প্রথম True পেলেই short-circuit করে থামে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম case-এ `subRoot=[4,1,2]` বড় tree-র বাঁ পাশে হুবহু বসে → True। দ্বিতীয় case-এ 4-এর নিচে বাড়তি node 0 থাকায় গঠন আর হুবহু মেলে না → False। `[1,1]`/`[1]`, একক node, আর `[1,2]`/`[2]` — সবগুলোতেই ঠিক match → True। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(m·n)** worst case — `m` = বড় tree-র node সংখ্যা, `n` = ছোট tree-র। outer walk প্রতিটা node ছোঁয় (O(m)), আর প্রতিটায় inner `is_same` সবচেয়ে খারাপ ক্ষেত্রে O(n) পর্যন্ত যেতে পারে। (Merkle-hashing দিয়ে গড়ে O(m + n)-এ নামানো যায়।)
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(m)** worst case — recursion call stack বড় tree-র height পর্যন্ত গভীর হতে পারে (একপাশে ঝোলা chain-এ O(m), balanced হলে O(log m)); inner `is_same`-ও ছোট tree-র height পর্যন্ত stack নেয়, কিন্তু সেটা বড়টার চেয়ে বেশি নয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `is_same`-এর None-গুলো ভুল ক্রমে দেখা: আগে "দুটোই None?" তারপর "একটা None?" — উল্টো করলে `None.val` ছোঁয়ার ঝুঁকি।
- partial match-কে যথেষ্ট ধরা: `sub`-এর সব node বড় tree-তে আছে কিন্তু গঠন আলাদা — তাও False হওয়া উচিত; পুরো নিচ পর্যন্ত মিলতে হবে।
- root None হলে True ফেরত দেওয়া — খালি বড় tree-তে non-empty `sub` থাকতে পারে না, তাই False।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Same Tree (#6)-এর pair-recursion equality আর Maximum Depth-জাতীয় "প্রতিটা node ঘোরা" traversal। দুটো এক হলে — একটা equality-check আরেকটা walk-এর ভেতরে — Subtree-of-Another-Tree সরাসরি দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Same Tree (এই problem-এর ভিত্তি; দুটো tree হুবহু এক কি না) —