027 — Serialize and Deserialize Binary Tree

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

Problem link ও উৎস

• Original source: Classic capstone interview problem (tree serialization round-trip)
• Platform: LeetCode — https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
• Topic: trees + recursion + string building
• Difficulty: Hard
• Pattern: traversal + format design (একটা traversal বেছে, null mark করে, একই ক্রমে rebuild)
• Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 07 trees (binary tree traversal), 06 recursion (pre-order recursion দিয়ে নামা ও ফেরা), আর 02 string building (node-গুলোকে একটা string-এ encode/decode)। তিন tool মিলে নিখুঁত round-trip।

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

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

তোমাকে একটা binary tree দেওয়া আছে। দুটো function লিখতে হবে:

• serialize(root) — পুরো tree-টাকে একটা single string-এ পরিণত করো।
• deserialize(s) — সেই string থেকে হুবহু একই tree আবার তৈরি করো।

শর্ত: deserialize(serialize(root)) যেন মূল tree-র সাথে structurally + value-তে অবিকল মেলে (round-trip)। node-এর value যেকোনো integer হতে পারে (negative-ও)।

উদাহরণ

        1
       / \
      2   3
         / \
        4   5

serialize -> "1,2,#,#,3,4,#,#,5,#,#"   (pre-order, # = null)
deserialize("1,2,#,#,3,4,#,#,5,#,#") -> ঠিক উপরের tree

Input ও output

উদাহরণ

tree: 1 -> (2, 3), 3 -> (4, 5)
serialize -> "1,2,#,#,3,4,#,#,5,#,#"
deserialize(উপরের) -> অবিকল একই tree

Edge case 1 (খালি tree): serialize(None) -> "#"
Edge case 2 (একটা node): serialize(node(7)) -> "7,#,#"
Edge case 3 (negative + multi-digit): node(-12) ঠিক round-trip হয়

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

ভাবো একটা পরিবার-বৃক্ষ (family tree) তুমি ফোনে একজনকে মুখে মুখে পড়ে শোনাচ্ছ, যাতে সে কাগজে হুবহু এঁকে নিতে পারে। তুমি বলো: "শীর্ষে রাম; রামের বাঁ-সন্তান শ্যাম; শ্যামের কোনো সন্তান নেই, নেই; রামের ডান-সন্তান যদু..." — প্রতিবার "কোনো সন্তান নেই" বলাটাই হলো null marker।

ওই "নেই"-গুলো না বললে শ্রোতা বুঝবে না কোথায় একটা শাখা শেষ হলো। বললেই সে নিখুঁতভাবে একই গাছ এঁকে ফেলতে পারে — এটাই null-marked traversal।

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

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

এই problem তিনটা আগের ধারণা জোড়া দেয়:

• 07 trees থেকে: একটা traversal (এখানে pre-order: root → left → right) যা প্রতিটা node ঠিক একবার ছোঁয়, structure-সহ।
• 06 recursion থেকে: serialize আর deserialize দুটোই recursion — নিচে নেমে subtree handle করে ফিরে আসা।
• 02 string building থেকে: node value আর null marker-গুলোকে একটা delimiter দিয়ে join করা (serialize) আর split করে token পড়া (deserialize)।

একা traversal দেয় ক্রম; একা recursion দেয় subtree handling; string building দেয় portable format। তিন মিলে reversible encoding।

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

লুকানো logic একটা null-marked traversal-এর অদ্বিতীয়তা: শুধু pre-order value list থেকে tree আবার বানানো যায় না (ambiguous), কিন্তু null-গুলোকেও mark করলে pre-order sequence অদ্বিতীয়ভাবে একটা tree নির্দিষ্ট করে।

কারণ: pre-order-এ প্রথম token সবসময় current subtree-র root; এরপর recursively পুরো বাঁ subtree, তারপর পুরো ডান subtree। null marker বলে দেয় কোথায় একটা subtree শেষ — তাই decode একই recursion ক্রমে token খেয়ে নিখুঁত rebuild করে।

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

• serialize-এ: একটা list/string buffer যেখানে pre-order-এ token জমে (শেষে delimiter দিয়ে join)।
• deserialize-এ: token-গুলোর উপর একটা iterator/index — recursion যত নামে, তত পরের token "খেয়ে" নেয়। আর অবশ্যই tree-র node structure নিজে।

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

Tree-টা nested, তাই একটা flat string-এ ভাঁজ করতে হলে এমন একটা ক্রম চাই যা structure ধরে রাখে — pre-order + null marker ঠিক সেটা দেয় (07 trees + 06 recursion)। delimiter-যুক্ত string portable: multi-digit আর negative value সহজে আলাদা করা যায় (02 string building)।

deserialize-এ একটা চলমান iterator efficient — প্রতিটা token ঠিক একবার consume হয়, আর recursion-এর structure নিজেই বলে দেয় পরের token কোন node-এর। তাই কোনো জটিল pointer arithmetic লাগে না।

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

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

প্রথম সরল চিন্তা: শুধু node value-গুলো pre-order-এ জমাও (null mark না করে), আর decode-এ কোনোভাবে structure আন্দাজ করার চেষ্টা।

উদাহরণ

serialize: [1, 2, 3, 4, 5]   (null বাদ)
deserialize: ??? কোনটা বাঁ, কোনটা ডান, কোথায় শাখা শেষ?

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

এটা slow নয় — এটা ভুল: null mark না থাকলে একটা pre-order value list বহু ভিন্ন tree থেকে আসতে পারে (ambiguous), তাই deserialize নিখুঁতভাবে কাজ করতেই পারে না। একটা single traversal থেকে tree পুনর্গঠনের জন্য হয় null marker লাগে, নয়তো দুটো traversal (যেমন pre+in-order, কিন্তু duplicate value-তে তাও ভাঙে)। null-marked pre-order সবচেয়ে পরিষ্কার সমাধান।

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

মূল observation: null-গুলোকেও token হিসেবে লিখলে একটা pre-order sequence অদ্বিতীয়ভাবে tree নির্দিষ্ট করে। null marker প্রতিটা subtree-র শেষ চিহ্নিত করে, তাই decode-এর সময় recursion ঠিক জানে কখন থামতে হবে আর কখন একটা নতুন subtree শুরু — কোনো ambiguity থাকে না।

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

serialize: pre-order recursion — node থাকলে তার value লেখো, তারপর বাঁ subtree, তারপর ডান subtree; node না থাকলে # লেখো। শেষে comma দিয়ে join।

deserialize: token-গুলোর উপর একটা iterator চালাও। পরের token নাও: # হলে None ফেরাও; নাহলে একটা node বানাও, তার বাঁ child recursively build করো (পরের token থেকে), তারপর ডান child — একই ক্রমে token consume হয়, tree আবার দাঁড়িয়ে যায়।

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

মোচড়: "শুধু value-গুলো জমাব" ভাবার বদলে ভাবো "null-গুলোও জমাব — তাহলে ক্রমটাই structure ধরে রাখে।" একটা ambiguous value-list একটা অদ্বিতীয়, reversible encoding-এ পরিণত হয়।

ছবিতে বোঝা

pre-order serialize (root → left → right, # = null):

উদাহরণ

        1
       / \
      2   3
         / \
        4   5

হাঁটার ক্রম:
  1 -> বাঁয়ে 2 -> 2-র বাঁ # -> 2-র ডান # -> ফিরে
  1-র ডান 3 -> 3-র বাঁ 4 -> 4-র বাঁ # -> 4-র ডান # -> ফিরে
  3-র ডান 5 -> 5-র বাঁ # -> 5-র ডান #

string: 1,2,#,#,3,4,#,#,5,#,#

decode: প্রথম token = root, তারপর recursively বাঁ subtree, তারপর ডান।
  '#' পেলে -> এখানে কোনো node নেই, None ফেরাও।

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

deserialize "1,#,#" (একটা মাত্র node 1):

1. token list: ["1", "#", "#"], iterator শুরুতে।
2. পরের token "1" → node(1) বানাও।
3. node(1)-র বাঁ child: পরের token "#" → None।
4. node(1)-র ডান child: পরের token "#" → None।
5. return node(1) — value 1, দুই child None। ✓ (serialize আবার "1,#,#" দেবে)

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

Python

Python

class TreeNode:
    """সাধারণ binary tree node (07 trees)।"""
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def serialize(root):
    """PRE-ORDER traversal (07) + recursion (06) + string building (02)।
    null-কেও '#' দিয়ে mark করি -> ক্রমটাই structure ধরে রাখে।"""
    parts = []

    def dfs(node):
        if node is None:
            parts.append("#")               # null marker
            return
        parts.append(str(node.val))         # root
        dfs(node.left)                       # পুরো বাঁ subtree
        dfs(node.right)                      # পুরো ডান subtree

    dfs(root)
    return ",".join(parts)                   # delimiter দিয়ে join


def deserialize(data):
    """একই pre-order ক্রমে token খেয়ে tree আবার বানাই (06 recursion)।"""
    tokens = iter(data.split(","))           # token-দের উপর চলমান iterator

    def build():
        tok = next(tokens)                   # পরের token consume
        if tok == "#":
            return None                      # subtree এখানে শেষ
        node = TreeNode(int(tok))            # multi-digit / negative ঠিক পার্স
        node.left = build()                  # বাঁ আগে (pre-order)
        node.right = build()                 # তারপর ডান
        return node

    return build()


def same_tree(p, q):
    # round-trip যাচাই: structure + value মেলে কি না
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    return p.val == q.val and same_tree(p.left, q.left) and same_tree(p.right, q.right)


def build_from_pairs(val, left=None, right=None):
    return TreeNode(val, left, right)


# ---- tests ----
# উদাহরণ tree: 1 -> (2, 3), 3 -> (4, 5)
root = build_from_pairs(1,
        build_from_pairs(2),
        build_from_pairs(3, build_from_pairs(4), build_from_pairs(5)))
s = serialize(root)
assert s == "1,2,#,#,3,4,#,#,5,#,#", s
assert same_tree(deserialize(s), root)        # round-trip নিখুঁত

# edge: খালি tree
assert serialize(None) == "#"
assert deserialize("#") is None

# edge: একটা node
one = build_from_pairs(7)
assert serialize(one) == "7,#,#"
assert same_tree(deserialize(serialize(one)), one)

# edge: negative + multi-digit value
neg = build_from_pairs(-12, build_from_pairs(345), build_from_pairs(-6))
assert same_tree(deserialize(serialize(neg)), neg)

# একপাশে হেলানো (left-skewed) tree
skew = build_from_pairs(1, build_from_pairs(2, build_from_pairs(3)))
assert same_tree(deserialize(serialize(skew)), skew)

# random fuzz: serialize -> deserialize সবসময় round-trip
import random
random.seed(27)

def random_tree(depth):
    if depth == 0 or random.random() < 0.3:
        return None
    return TreeNode(random.randint(-20, 20),
                    random_tree(depth - 1),
                    random_tree(depth - 1))

for _ in range(500):
    t = random_tree(5)
    assert serialize(deserialize(serialize(t))) == serialize(t)
    assert same_tree(deserialize(serialize(t)), t)

print("সব test pass!")

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

• serialize.dfs — pre-order: node থাকলে value, তারপর বাঁ subtree, তারপর ডান; null হলে #। ,.join দিয়ে portable string।
• deserialize.build — token iterator থেকে একটা একটা করে consume; # → None, নাহলে node বানিয়ে বাঁ তারপর ডান recursively (একই pre-order ক্রম)।
• int(tok) — multi-digit আর negative value সঠিক পার্স করে (তাই delimiter দরকার)।
• same_tree — round-trip-এ structure + value মেলে কি না যাচাইয়ের obviously-correct reference।
• random fuzz 500টা random tree-র round-trip নিশ্চিত করে।

Output মিলিয়ে দেখা

উদাহরণ tree serialize হয় "1,2,#,#,3,4,#,#,5,#,#", আর deserialize ঠিক একই tree ফেরায় (same_tree pass)। খালি tree ("#"), একক node ("7,#,#"), negative+multi-digit, আর left-skewed tree সব round-trip করে। শেষে 500 random tree-তে serialize(deserialize(serialize(t))) == serialize(t) ধরে রাখে। শেষে print: সব test pass!।

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

সময়

serialize O(n) (প্রতিটা node + null একবার), deserialize O(n) (প্রতিটা token একবার consume)। n = node সংখ্যা।

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

O(n) — output string + recursion stack (worst case skewed tree-তে stack depth O(n), balanced-এ O(log n))।

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

• null marker বাদ দেওয়া — তাহলে pre-order ambiguous, deserialize নিখুঁত হবে না।
• delimiter ছাড়া concat করা — multi-digit (12) বা negative (-3) value আলাদা করা যায় না; comma রাখো।
• deserialize-এ একই iterator/index share না করা (প্রতি call নতুন split) — token-ক্রম ভেঙে যাবে; একটাই চলমান iterator চাই।
• বাঁ-র আগে ডান build করা — serialize pre-order হলে deserialize-ও বাঁ আগে হতে হবে, নাহলে mirror হয়ে যায়।

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

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

ভিত্তি: binary tree traversal (07 trees, ../../07-trees/-এর pre-order) + recursion (06 recursion, নিচে নেমে subtree handle করে ফেরা) + string join/split (02 string building)। তিনটা cold-এ জানা থাকলে এই round-trip নিজে থেকে দাঁড়ায়।

পরের অনুশীলন

• Serialize and Deserialize BST (BST property কাজে লাগিয়ে আরো compact) — https://leetcode.com/problems/serialize-and-deserialize-bst/
• Construct Binary Tree from Preorder and Inorder Traversal — https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
• Encode N-ary Tree to Binary Tree — https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/

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

Traversal + format design: একটা traversal (pre-order) বেছে, null-গুলোকে mark করে structure-সহ একটা reversible string বানানো, তারপর একই ক্রমে token consume করে tree rebuild করা। trees + recursion + string building-এর canonical মেলবন্ধন।

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

ভবিষ্যতের আমাকে: "tree-কে string-এ, আবার ফেরত" দেখলেই null-marked pre-order মনে করবে। serialize: value, তারপর বাঁ, তারপর ডান; null হলে #; comma দিয়ে join। deserialize: একটাই iterator-এ token খাও — # → None, নাহলে node বানিয়ে বাঁ তারপর ডান। null marker-ই ক্রমকে অদ্বিতীয় করে — এটাই round-trip-এর চাবি।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।