পাইথনে একটি ট্রি অন্য ট্রির সাবট্রি কিনা যাচাই করা

দুটি বাইনারি ট্রি দেওয়া থাকলে, দ্বিতীয় ট্রি (target) প্রথম ট্রির (root) সাবট্রি কিনা যাচাই করতে হবে।

উদাহরণ: রুট=৬(৪(৩,৫), ১০), টার্গেট=৪(৩,৫) → True।

রিকার্সিভ সমাধান

• দুটোই None → True।
• একটি None → False।
• যদি root.val == target.val: দুই সাবট্রি রিকার্সিভলি মিলিয়ে দেখুন (solve(left, left) and solve(right, right))।
• অন্যথায়: রুটের বাম বা ডান সাবট্রি-তে টার্গেট খুঁজুন (solve(left, target) or solve(right, target))।

পাইথন কোড

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root, target):
        if root is None and target is None:
            return True
        if root is None or target is None:
            return False
        if root.val == target.val:
            return (self.solve(root.left, target.left) and
                    self.solve(root.right, target.right))
        else:
            return (self.solve(root.left, target) or
                    self.solve(root.right, target))

# টেস্ট
ob = Solution()
root1 = TreeNode(6, TreeNode(4, TreeNode(3), TreeNode(5)), TreeNode(10))
root2 = TreeNode(4, TreeNode(3), TreeNode(5))
print(ob.solve(root1, root2))  # True

টাইম কমপ্লেক্সিটি: O(n×m) ওয়ার্স্ট কেস (n, m = নোড সংখ্যা), স্পেস: O(h)। বড় ট্রির জন্য KMP/স্ট্রিং ম্যাচিং অপ্টিমাইজেশন সম্ভব।