পাইথনে বাইনারি সার্চ ট্রি সিরিয়ালাইজ ও ডিসিরিয়ালাইজ করা

সমস্যা বিবরণ

বাইনারি সার্চ ট্রি (BST) কে সিরিয়ালাইজ (বাইট সিকোয়েন্সে রূপান্তর) এবং ডিসিরিয়ালাইজ (ফিরে ট্রি বানানো) করার অ্যালগরিদম ডিজাইন করতে হবে। সিরিয়ালাইজেশন ডেটা স্ট্রাকচারকে ফাইল, মেমরি বা নেটওয়ার্কের মাধ্যমে ট্রান্সমিট করার জন্য উপযোগী করে তোলে।

উদাহরণ

ইনপুট: [5,2,9,1,3,7]

সিরিয়ালাইজড আউটপুট: 5.2.9.1.3.7.N.N.N.N.N.N.N

ডিসিরিয়ালাইজড আউটপুট (ইনঅর্ডার ট্রাভার্সাল): 1, 2, 3, 5, 7, 9

সমাধানের পদ্ধতি

লেভেল অর্ডার (BFS) ট্রাভার্সাল ব্যবহার করে সিরিয়ালাইজেশন এবং স্ট্যাক-ভিত্তিক পার্সিং দিয়ে ডিসিরিয়ালাইজেশন করা হয়।

সিরিয়ালাইজেশন (BFS)

1. কিউতে রুট নোড দিয়ে শুরু করুন
2. কিউ খালি না হওয়া পর্যন্ত:
   • কিউ থেকে নোড ডিকিউ করুন
   • নোড থাকলে ভ্যালু, না থাকলে "N" রেজাল্টে যোগ করুন
   • নোড থাকলে তার বাম ও ডান চাইল্ড কিউতে এনকিউ করুন (নাল হলে None)
3. রেজাল্টকে ডট (.) দিয়ে জড়িয়ে স্ট্রিং বানান

ডিসিরিয়ালাইজেশন

1. স্ট্রিংকে ডট দিয়ে স্প্লিট করুন
2. প্রথম ভ্যালু "N" হলে None রিটার্ন করুন
3. স্ট্যাক ব্যবহার করে ট্রি পুনঃনির্মাণ করুন:
   • বর্তমান নোডের বাম ও ডান চাইল্ড সিকোয়েনশিয়ালি প্রসেস করুন

পাইথন কোড

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

class Codec:
    def serialize(self, root):
        if not root:
            return "N"
        res = []
        queue = [root]
        while queue:
            current = queue.pop(0)
            if current:
                res.append(str(current.data))
                queue.append(current.left)
                queue.append(current.right)
            else:
                res.append("N")
        return ".".join(res)
    
    def deserialize(self, data):
        if data == "N":
            return None
        vals = data.split(".")
        root = TreeNode(int(vals[0]))
        queue = [root]
        i = 1
        while queue and i < len(vals):
            node = queue.pop(0)
            if vals[i] != "N":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if i < len(vals) and vals[i] != "N":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

# টেস্ট
def make_tree(elements):
    root = TreeNode(elements[0])
    for el in elements[1:]:
        # BST ইনসার্ট লজিক
        cur = root
        while True:
            if el < cur.data:
                if cur.left: cur = cur.left
                else: cur.left = TreeNode(el); break
            else:
                if cur.right: cur = cur.right
                else: cur.right = TreeNode(el); break
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=", ")
        inorder(root.right)

ob = Codec()
root = make_tree([5,2,9,1,3,7])
ser = ob.serialize(root)
print('Serialization:', ser)
print('Deserialized inorder:', end=" ")
inorder(ob.deserialize(ser))

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N) — N = নোড সংখ্যা
• স্থান জটিলতা: O(N) — কিউ ও আউটপুট স্ট্রিংয়ের জন্য

মূল বিষয়বস্তু

• BFS ট্রাভার্সাল ট্রি স্ট্রাকচার সংরক্ষণে সহায়ক
• "N" মার্কার নাল পয়েন্টার নির্দেশ করে
• এই প্যাটার্ন ডিস্ট্রিবিউটেড সিস্টেম, ক্যাশিং, ডাটাবেসে ব্যাপক ব্যবহৃত