020 — Subtree of Another Tree

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• 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-এ প্রয়োগ করা

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে দুটো binary tree দেওয়া আছে — একটা বড় root, আর একটা ছোট subRoot। তোমার কাজ: বলা যে বড় tree-র মধ্যে কোথাও এমন কোনো node আছে কি না, যেখান থেকে শুরু করলে নিচের পুরো subtree-টা হুবহু subRoot-এর সমান (একই গঠন, একই value)।

মনে রেখো — "subtree" মানে কোনো একটা node আর তার নিচের সবকিছু, মাঝপথে কেটে নেওয়া অংশ নয়। তাই match হতে হলে নিচ পর্যন্ত পুরোটা মিলতে হবে।

উদাহরণ

     3              4         subRoot পুরোটা root-এর বাঁ পাশে বসে আছে
    / \            / \
   4   5          1   2       → answer: True
  / \
 1   2

Input ও 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

চেনা উদাহরণে বোঝা

ভাবো তোমার হাতে একটা ছোট পরিবার-গাছের ছবি (subRoot), আর একটা বিশাল বংশলতিকা (root)। তুমি বড় গাছের প্রতিটা মানুষের কাছে গিয়ে জিজ্ঞেস করছ: "তোমাকে শিকড় ধরে নিচের দিকে দেখলে কি ঠিক এই ছোট ছবিটার মতো দেখায়?" কারো ক্ষেত্রে পুরো নিচটা হুবহু মিললেই তুমি বলবে "পেয়েছি"। প্রতিটা ব্যক্তির কাছে প্রশ্ন = outer walk; নিচটা মিলিয়ে দেখা = inner compare।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা সরাসরি Same Tree (#6)-এর উপর দাঁড়ায়। Same Tree বলত "এই দুটো tree কি ঠিক এক?" — এখানে আমরা সেই is_same যাচাইটা বড় tree-র প্রতিটা node-এ চালাই: "এই node থেকে শুরু করা subtree কি subRoot-এর সমান?" একটায় হ্যাঁ পেলেই উত্তর True। মানে একটা inner equality-check + একটা outer "সব node ঘোরা" traversal।

ভেতরের যুক্তি

লুকানো 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 থেকে পুরো গঠন মেলায়।

কী দিয়ে তথ্য রাখব

কোনো extra data structure লাগে না — দুটো recursion: একটা outer (is_subtree, সব candidate node ঘোরে) আর একটা inner (is_same, দুটো tree তুলনা করে)। দুই tree নিজেরাই data structure, আর call stack কোথায় আছি মনে রাখে।

এটি কেন উপযুক্ত

Tree self-similar (concept.md দেখো): প্রতিটা node নিজেই একটা পূর্ণ subtree-র root। তাই "প্রতিটা node-কে সম্ভাব্য শুরু ধরে যাচাই করা" recursion দিয়ে নিখুঁত খাপ খায় — outer recursion candidate বাছে, inner recursion লক্ষ্য করে দুটো গঠন একসাথে মেলায়। কোনো index বা পাশের buffer লাগে না, কারণ tree-র আকৃতিই navigation দেয়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: বড় tree-র প্রতিটা node-কে সম্ভাব্য শুরু ধরো, আর প্রতিটার জন্য পুরো is_same যাচাই চালাও।

উদাহরণ

1) root-এর সব node তালিকা করো: 3, 4, 5, 1, 2
2) প্রতিটার জন্য is_same(node, subRoot) চালাও
3) কোথাও True পেলে থামো; না পেলে False

মজার ব্যাপার — এই "brute force"-টাই এখানে আদর্শ সমাধান, কারণ আমাদের সত্যিই প্রতিটা সম্ভাব্য শুরু দেখতে হয়।

কোথায় বেশি কাজ হচ্ছে

এটা ভয়ংকর ধীর নয়, তবে worst case-এ একটু খরচালি: প্রতিটা node-এ (mটা) inner compare চলতে পারে যা ছোট tree-র আকার (n) পর্যন্ত যায়, তাই O(m·n)। দুটো tree যদি অনেক একইরকম প্রায়-mil অংশে ভরা থাকে, তবে compare বারবার অনেকদূর গিয়ে শেষে fail করে — সেটাই অপচয়। (string-hashing/Merkle hash দিয়ে গড়ে দ্রুত করা যায়, কিন্তু সেটা পরের ধাপ।)

যে বিষয়টি খেয়াল করতে হবে

মূল observation: "subtree খোঁজা" = "প্রতিটা node-এ একটা Same-Tree যাচাই চালানো।" দুটো আলাদা সমস্যা নয় — একটা পরিচিত সমস্যা (Same Tree) আরেকটা traversal-এর ভেতরে বসানো। আর match-টা হতে হবে নিচ পর্যন্ত পুরো, মাঝপথে থামলে চলবে না।

আরও কম কাজে সমাধান

দুই recursion আলাদা করে ভাবো। outer (is_subtree) একটা preorder walk: এই node-এ মেলে কি? না হলে বাঁয়ে বা ডানে খোঁজো (OR)। inner (is_same) একটা lockstep compare: দুটো গঠন একসাথে নামে, এক জায়গায় গরমিল পেলেই False। প্রথম True পেলেই or-এর short-circuit বাকিটা থামিয়ে দেয়।

ভাবনার পরিবর্তন

মোচড়: নতুন কিছু আবিষ্কার করতে যেও না। মনে করো "আমার কাছে তো আগে থেকেই Same Tree আছে" — শুধু সেটা প্রতিটা node-এ চালাও। দুটো প্রশ্ন আলাদা রাখো: (১) এখান থেকে মেলে কি (is_same)? (২) আর কোথাও মেলে কি (left/right-এ recurse)? এই দুটো গুলিয়ে ফেললেই bug।

ছবিতে বোঝা

বাইরের walk প্রতিটা node-এ is_same চালায়; node 4-এ গিয়ে পুরো গঠন মেলে:

উদাহরণ

        3            is_same(3, sub)? না (4 ≠ 3)
       / \
      4   5          is_same(4, sub)? হ্যাঁ ✓ → True
     / \
    1   2            (এখানে আর নামার দরকার নেই)

ছোট input-এ ধাপে ধাপে

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) আর দেখার দরকার নেই।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

প্রথম case-এ subRoot=[4,1,2] বড় tree-র বাঁ পাশে হুবহু বসে → True। দ্বিতীয় case-এ 4-এর নিচে বাড়তি node 0 থাকায় গঠন আর হুবহু মেলে না → False। [1,1]/[1], একক node, আর [1,2]/[2] — সবগুলোতেই ঠিক match → True। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

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)-এ নামানো যায়।)

অতিরিক্ত জায়গা

O(m) worst case — recursion call stack বড় tree-র height পর্যন্ত গভীর হতে পারে (একপাশে ঝোলা chain-এ O(m), balanced হলে O(log m)); inner is_same-ও ছোট tree-র height পর্যন্ত stack নেয়, কিন্তু সেটা বড়টার চেয়ে বেশি নয়।

যে ভুলগুলো এড়াতে হবে

• is_same-এর None-গুলো ভুল ক্রমে দেখা: আগে "দুটোই None?" তারপর "একটা None?" — উল্টো করলে None.val ছোঁয়ার ঝুঁকি।
• partial match-কে যথেষ্ট ধরা: sub-এর সব node বড় tree-তে আছে কিন্তু গঠন আলাদা — তাও False হওয়া উচিত; পুরো নিচ পর্যন্ত মিলতে হবে।
• root None হলে True ফেরত দেওয়া — খালি বড় tree-তে non-empty sub থাকতে পারে না, তাই False।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: Same Tree (#6)-এর pair-recursion equality আর Maximum Depth-জাতীয় "প্রতিটা node ঘোরা" traversal। দুটো এক হলে — একটা equality-check আরেকটা walk-এর ভেতরে — Subtree-of-Another-Tree সরাসরি দাঁড়িয়ে যায়।

পরের অনুশীলন

• 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/

কৌশলটি মনে রাখুন

Nested recursion (match-at-every-node): একটা চেনা compare (is_same) নাও, আর সেটা একটা outer traversal-এর প্রতিটা node-এ চালাও; প্রথম সফলতায় or দিয়ে থামো। যখনই "X কি কোথাও Y-এর মতো দেখায়" টাইপ প্রশ্ন আসে, এই walk-plus-compare কঙ্কালটা মনে করবে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।