006 — Same Tree¶
Source¶
- Original source: Classic binary tree comparison exercise
- Platform: LeetCode — https://leetcode.com/problems/same-tree/
- Topic: trees
- Difficulty: Easy
- Pattern: Pair recursion
- Basic idea inherited from: Subtree comparison pattern — একটা tree-র বদলে দুটো tree একসাথে নামিয়ে মেলানো
1. Problem in simple words¶
তোমাকে দুটো binary tree-র root দেওয়া আছে (p আর q)। তোমার কাজ: বলো ওরা হুবহু একরকম কিনা — মানে একই shape (structure) আর প্রতিটা মিলে যাওয়া জায়গায় একই value। দুটো শর্তই মানতে হবে।
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:
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 দুটো সবসময় মিল-অবস্থানে থাকে।
6. Real-life analogy¶
দুটো বাড়ির blueprint পাশাপাশি রেখে মেলানোর কথা ভাবো। তুমি একই ঘর ধরে ধরে দুটোতে এগোও: দরজা একই জায়গায়? জানালার সংখ্যা এক? যেই প্রথম একটা অমিল পাও — একটাতে ঘর আছে, অন্যটাতে নেই, বা মাপ আলাদা — তখনই বলে দাও "এক না।" সব ঘর মিলে গেলে তবেই "হুবহু এক।"
7. Visual explanation¶
দুই tree-তে একই অবস্থান একসাথে তুলনা হয় (↕ মানে এই জোড়া এখন মেলানো হচ্ছে):
p q
1 ↕ 1 ← 1 == 1, আরও গভীরে নামে
/ \ / \
2 ↕ 2 2 2 ← 2 == 2
\ \
∅ ↕ ∅ ← দুজনেরই left None: ঠিক আছে
কোথাও একটা node, অন্যটা None হলে → সঙ্গে সঙ্গে False
8. Example input and output¶
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 (দুটোই খালি)
9. Brute force thinking¶
প্রথম সরল চিন্তা: দুই tree-কে আলাদা করে কোনো traversal (যেমন preorder, None marker সহ) দিয়ে list বানাই, তারপর দুই list সমান কিনা মেলাই।
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 মেলানোর দরকারই নেই।
14. Step-by-step dry run¶
Input p = [1,2], q = [1,null,2] (p: root 1 left 2; q: root 1 right 2):
same(p=1, q=1): দুটোই node, 1 == 1 → এখন left-জোড়া আর right-জোড়া দেখো।- বাঁ-জোড়া:
same(p.left = 2, q.left = None)→ একটা node, একটা None → False। and-এর প্রথম অংশই False হওয়ায় right-জোড়া আর দেখা হয় না।- পুরো ফলাফল → False (shape আলাদা)।
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_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প্রথম মিথ্যেতে থেমে যায়।
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!।
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 হয়ে যায়, ভুল।
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 করে) — https://leetcode.com/problems/symmetric-tree/ (এই tracker-এর #7)
- Subtree of Another Tree (Same Tree-কে প্রতিটা node-এ চালাও) — https://leetcode.com/problems/subtree-of-another-tree/ (#20)
- Leaf-Similar Trees (দুই tree-র leaf sequence এক কিনা) — https://leetcode.com/problems/leaf-similar-trees/
23. Pattern learned¶
Pair recursion: function এক node না, এক জোড়া node নেয়; আগে None-cases সামলাও, তারপর value মেলাও, তারপর and দিয়ে দুই দিকে সমান্তরালে নামো। short-circuit প্রথম অমিলে থামিয়ে দেয়।
24. Final summary¶
ভবিষ্যতের আমাকে: "Same Tree = দুই tree পা মিলিয়ে নামাও; None-জোড়া, value, তারপর and দিয়ে দুই দিক।" যখনই দুই tree তুলনা বা match করতে হবে, এই জোড়া-recursion মনে পড়বে। আসল চাবি: structure মেলে None-গুলোর তুলনায়, value না।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।