020 — Subtree of Another Tree¶
Source¶
- Original source: Classic "is this tree contained inside that tree" exercise
- Platform: LeetCode — https://leetcode.com/problems/subtree-of-another-tree/
- Topic: trees
- Difficulty: Medium
- Pattern: Subtree comparison
- Basic idea inherited from: Same Tree (#6), প্রতিটা node-এ প্রয়োগ করা
1. Problem in simple words¶
তোমাকে দুটো binary tree দেওয়া আছে — একটা বড় root, আর একটা ছোট subRoot। তোমার কাজ: বলা যে বড় tree-র মধ্যে কোথাও এমন কোনো node আছে কি না, যেখান থেকে শুরু করলে নিচের পুরো subtree-টা হুবহু subRoot-এর সমান (একই গঠন, একই value)।
মনে রেখো — "subtree" মানে কোনো একটা node আর তার নিচের সবকিছু, মাঝপথে কেটে নেওয়া অংশ নয়। তাই match হতে হলে নিচ পর্যন্ত পুরোটা মিলতে হবে।
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-এর ভেতরে আরেকটা যাচাই:
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 দেয়।
6. Real-life analogy¶
ভাবো তোমার হাতে একটা ছোট পরিবার-গাছের ছবি (subRoot), আর একটা বিশাল বংশলতিকা (root)। তুমি বড় গাছের প্রতিটা মানুষের কাছে গিয়ে জিজ্ঞেস করছ: "তোমাকে শিকড় ধরে নিচের দিকে দেখলে কি ঠিক এই ছোট ছবিটার মতো দেখায়?" কারো ক্ষেত্রে পুরো নিচটা হুবহু মিললেই তুমি বলবে "পেয়েছি"। প্রতিটা ব্যক্তির কাছে প্রশ্ন = outer walk; নিচটা মিলিয়ে দেখা = inner compare।
7. Visual explanation¶
বাইরের walk প্রতিটা node-এ is_same চালায়; node 4-এ গিয়ে পুরো গঠন মেলে:
3 is_same(3, sub)? না (4 ≠ 3)
/ \
4 5 is_same(4, sub)? হ্যাঁ ✓ → True
/ \
1 2 (এখানে আর নামার দরকার নেই)
8. Example input and output¶
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
9. Brute force thinking¶
প্রথম সরল চিন্তা: বড় tree-র প্রতিটা node-কে সম্ভাব্য শুরু ধরো, আর প্রতিটার জন্য পুরো is_same যাচাই চালাও।
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।
14. Step-by-step dry run¶
root = [3,4,5,1,2], subRoot = [4,1,2]:
is_subtree(3, sub):is_same(3, 4)? না (3 ≠ 4)। তাই বাঁ/ডানে খোঁজো।is_subtree(4, sub):is_same(4, 4)? val মেলে → left:is_same(1,1)✓, right:is_same(2,2)✓ → True।or-এর বাঁ দিক True হয়ে গেছে → পুরো উত্তর True, ডান (5) আর দেখার দরকার নেই।
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_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 করে থামে।
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!।
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।
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 হুবহু এক কি না) — https://leetcode.com/problems/same-tree/ (এই tracker-এর #6)
- Count Univalue Subtrees (কয়টা subtree একই value-র, একই "প্রতি node-এ যাচাই" কাঠামো) — https://leetcode.com/problems/count-univalue-subtrees/
- Most Frequent Subtree Sum (প্রতিটা subtree serialize/hash করে গোনা) — https://leetcode.com/problems/most-frequent-subtree-sum/
23. Pattern learned¶
Nested recursion (match-at-every-node): একটা চেনা compare (is_same) নাও, আর সেটা একটা outer traversal-এর প্রতিটা node-এ চালাও; প্রথম সফলতায় or দিয়ে থামো। যখনই "X কি কোথাও Y-এর মতো দেখায়" টাইপ প্রশ্ন আসে, এই walk-plus-compare কঙ্কালটা মনে করবে।
24. Final summary¶
ভবিষ্যতের আমাকে: "subtree খোঁজা = প্রতিটা node-এ Same-Tree চালানো; নিচ পর্যন্ত পুরো মিলতে হবে।" inner compare আর outer walk আলাদা রাখো, আর or-এর short-circuit-কে কাজে লাগাও। 'এই গঠনটা কি ওই বড় গঠনের ভেতরে বসে আছে' টাইপ problem দেখলেই এই nested-recursion চালটা মনে করবে।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।