Skip to content

024 — Serialize and Deserialize Binary Tree

Source

1. Problem in simple words

তোমাকে দুটো function লিখতে হবে। serialize(root) একটা binary tree-কে একটা string-এ রূপান্তর করে (যাতে ফাইলে রাখা বা network-এ পাঠানো যায়)। deserialize(data) সেই string থেকে হুবহু একই tree আবার বানিয়ে ফেরত দেয়। শর্ত: deserialize(serialize(root)) করলে গঠন আর value-সহ মূল tree-টাই ফিরে পেতে হবে।

মূল চ্যালেঞ্জ: গঠনটাও বাঁচাতে হবে — শুধু value-গুলো জানা যথেষ্ট নয়, কোন node-এর কোন দিকে কে আছে, কোথায় ফাঁকা — সব string-এ encode করতে হবে।

        1                serialize → "1,2,3,#,#,4,5,#,#,#,#"
       / \                          (# = None marker, preorder ক্রমে)
      2   3
         / \
        4   5            deserialize → ঠিক এই tree-ই ফিরিয়ে আনে

2. Which basic idea does this inherit from?

ভিত্তি preorder traversal (Node → Left → Right) — কিন্তু একটা গুরুত্বপূর্ণ যোগ: None marker (#)। সাধারণ preorder শুধু value দেয়, যা থেকে গঠন অদ্বিতীয়ভাবে ফেরানো যায় না। কিন্তু প্রতিটা ফাঁকা child-এর জায়গায় একটা marker রাখলে preorder-টা অদ্বিতীয় হয়ে যায় — তখন একই preorder ক্রমে পড়তে পড়তে tree-টা সরাসরি গড়ে তোলা যায় (Construct-from-preorder #21-এর জ্ঞাতি, কিন্তু এখানে inorder লাগে না, marker-ই যথেষ্ট)।

3. What is the hidden math or logic?

লুকানো logic হলো marker-সহ preorder-এর অদ্বিতীয়তা:

serialize(node):
    node None হলে  → "#" লেখো
    নইলে           → node.val লেখো, তারপর serialize(left), তারপর serialize(right)

deserialize(tokens):  # একই preorder ক্রমে পড়ো
    পরের token নাও
    "#" হলে        → None ফেরত
    নইলে           → node বানাও, node.left = deserialize(...), node.right = deserialize(...)

মূল বুদ্ধি: serialize আর deserialize ঠিক একই ক্রমে (preorder) node ছোঁয়, তাই একটা চলন্ত pointer দিয়ে token-গুলো পরপর খেয়ে গেলেই গঠন নিখুঁতভাবে পুনর্গঠিত হয়।

4. Which data structure is needed?

serialize-এ একটা list/string-builder (token জমায়, শেষে join), deserialize-এ token-গুলোর একটা iterator বা deque (পরের token O(1)-তে তুলতে) আর recursion call stack। দুই দিকেই tree-র self-similarity-র উপর recursion চলে; marker # দিয়ে ফাঁকা স্থান চিহ্নিত।

5. Why this data structure fits

preorder এমন একটা ক্রম যেখানে root আগে আসে — তাই deserialize পড়ার সময় আগে parent বানিয়ে তারপর child বসাতে পারে, ঠিক যেভাবে serialize লিখেছিল। একটা deque/iterator token-গুলো একই ক্রমে এক-এক করে দেয়, কোনো index-হিসাব ছাড়াই। আর marker # ছাড়া preorder ambiguous হতো (দুটো ভিন্ন tree একই value-ক্রম দিতে পারে) — marker সেই ফাঁক বন্ধ করে গঠন অদ্বিতীয় করে।

6. Real-life analogy

ভাবো তুমি একটা পরিবার-গাছ ফোনে কাউকে মুখে বলে দিচ্ছ। তুমি বলবে: "আগে নিজের নাম, তারপর বাঁ সন্তানের পুরো শাখা, তারপর ডান সন্তানের পুরো শাখা। যেখানে কেউ নেই, সেখানে বলবে 'খালি'।" ওপ্রান্তের লোক ঠিক একই ক্রমে শুনে শুনে কাগজে গাছটা আঁকবে — 'খালি' শুনলে সেদিকে কিছু আঁকবে না। 'খালি' শব্দটাই (marker) নিশ্চিত করে দু'জনের আঁকা গাছ হুবহু এক হবে।

7. Visual explanation

preorder ক্রমে value আর # (None) লেখা হয়; deserialize সেই tokens একই ক্রমে খায়:

        1
       / \
      2   3
         / \
        4   5

preorder tokens:  1  2  #  #  3  4  #  #  5  #  #
                  ↑root ↑2-leaf  ↑3  ↑4-leaf  ↑5-leaf

8. Example input and output

Input : root = [1,2,3,null,null,4,5]
serialize  -> "1,2,#,#,3,4,#,#,5,#,#"
deserialize-> ওই string থেকে হুবহু আগের tree

Edge  : root = []          -> serialize "#"        -> deserialize None
Edge  : root = [1]         -> serialize "1,#,#"    -> একটামাত্র node 1
Edge  : root = [1,2]       -> serialize "1,2,#,#,#"-> 1, বাঁ child 2

মূল চুক্তি: যেকোনো tree-র জন্য deserialize(serialize(t)) == t (গঠন+value)

9. Brute force thinking

প্রথম সরল চিন্তা — marker ছাড়া: শুধু preorder value-গুলো জমাই, আর deserialize-এ অনুমান করি কোথায় ভাঙব।

1) serialize: শুধু value preorder-এ লেখো → "1,2,3,4,5"
2) deserialize: প্রথমটা root, তারপর... কোনগুলো বাঁ, কোনগুলো ডান?
3) → অনুমান করার কোনো নিশ্চিত উপায় নেই (গঠন হারিয়ে গেছে)

10. Why brute force is slow

এটা ধীর নয় — এটা সরাসরি ভুল। marker ছাড়া একই value-sequence একাধিক ভিন্ন গঠনের tree থেকে আসতে পারে (যেমন [1,2]-তে 2 বাঁ না ডান child তা বোঝা যায় না)। তাই deserialize অদ্বিতীয় উত্তর দিতে পারে না। সমাধান: প্রতিটা ফাঁকা child-এর জায়গায় একটা None marker যোগ করা — সামান্য বেশি জায়গা, কিন্তু গঠন সম্পূর্ণ পুনরুদ্ধারযোগ্য।

11. Key observation

মূল observation: প্রতিটা ফাঁকা child-এও একটা marker রাখলে preorder অদ্বিতীয় হয়ে যায়। তখন deserialize-এর আর "কোথায় ভাঙব" ভাবতে হয় না — সে শুধু token-গুলো একই preorder ক্রমে খায়: value পেলে node বানায় (আগে বাঁ, পরে ডান recurse), # পেলে None ফেরত দেয়।

12. Optimized intuition

serialize একটা preorder DFS: None হলে #, নইলে value তারপর left তারপর right — সব token একটা list-এ, শেষে কমা দিয়ে join। deserialize একটা iterator বানায় token-গুলোর উপর; একটা helper পরের token নেয় — # হলে None, নইলে node বানিয়ে node.left = build(), node.right = build()। যেহেতু serialize ও deserialize একই ক্রমে চলে, pointer নিজে থেকেই ঠিক জায়গায় থাকে। দুই দিকই O(n)।

13. Thinking tweak

মোচড়: "string-টা কীভাবে parse করব" নিয়ে আটকে যেও না। মনে রাখো — serialize আর deserialize একই recursion, একই preorder ক্রম; একটা লেখে, আরেকটা পড়ে। মূল চাবি None marker: সেটা থাকলে গঠন অদ্বিতীয়, আর একটা চলন্ত iterator/pointer-ই বাকি কাজ করে দেয়। আলাদা index গোনা বা inorder লাগে না (#21-এর চেয়ে এখানে সহজ)।

14. Step-by-step dry run

deserialize tokens ["1","2","#","#","3","4","#","#","5","#","#"], iterator সামনে থেকে খায়:

  1. build(): token "1" → node 1। এখন node.left = build()।
  2. build(): token "2" → node 2। node.left = build() → token "#" → None। node.right = build() → "#" → None। node 2 (leaf) ফেরত। (1-এর বাঁ = 2)
  3. ফিরে 1-এর node.right = build(): token "3" → node 3।
  4. 3-এর বাঁ: build() → "4" → node 4; তার দুই child "#","#" → None,None (leaf 4)।
  5. 3-এর ডান: build() → "5" → node 5; দুই child "#","#" → None,None (leaf 5)।
  6. গঠন: 1 → (2, 3), 3 → (4, 5)। ঠিক মূল tree।

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 বানায় (test setup-এর জন্য)।"""
    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 serialize(root):
    out = []

    def dfs(node):
        if node is None:
            out.append("#")              # None marker
            return
        out.append(str(node.val))        # preorder: value আগে
        dfs(node.left)                   # তারপর বাঁ
        dfs(node.right)                  # তারপর ডান

    dfs(root)
    return ",".join(out)


def deserialize(data):
    tokens = iter(data.split(","))       # একই preorder ক্রমে পড়ব

    def build():
        val = next(tokens)
        if val == "#":                   # None marker → ফাঁকা
            return None
        node = TreeNode(int(val))
        node.left = build()              # serialize-এর মতোই বাঁ আগে
        node.right = build()             # তারপর ডান
        return node

    return build()


def same_tree(a, b):
    """round-trip যাচাইয়ের helper: দুই tree হুবহু এক কি না।"""
    if a is None and b is None:
        return True
    if a is None or b is None or a.val != b.val:
        return False
    return same_tree(a.left, b.left) and same_tree(a.right, b.right)


# ---- tests ----
t = build_tree([1, 2, 3, None, None, 4, 5])
assert serialize(t) == "1,2,#,#,3,4,#,#,5,#,#"
assert same_tree(deserialize(serialize(t)), t)          # round-trip ঠিক

assert serialize(build_tree([])) == "#"                 # খালি tree
assert deserialize("#") is None
assert same_tree(deserialize(serialize(build_tree([1]))), build_tree([1]))
assert same_tree(deserialize(serialize(build_tree([1, 2]))), build_tree([1, 2]))

neg = build_tree([-7, -3, 9])                            # ঋণাত্মক value-ও টেকে
assert same_tree(deserialize(serialize(neg)), neg)
print("সব test pass!")

16. Line-by-line code explanation

  • serialize.dfs: None হলে "#" (marker), নইলে value লিখে আগে বাঁ তারপর ডান — খাঁটি preorder।
  • ",".join(out) — সব token কমা দিয়ে একটা string-এ; এটাই serialize-এর আউটপুট।
  • tokens = iter(data.split(",")) — string ভেঙে token, তার উপর একটা iterator; next() পরের token O(1)-তে দেয়।
  • build()-এ next(tokens) — serialize যে ক্রমে লিখেছিল, ঠিক সেই ক্রমে পড়ছি, তাই pointer নিজেই সঠিক জায়গায়।
  • if val == "#": return None — marker পেলে এই দিক ফাঁকা।
  • node.left = build(); node.right = build() — serialize-এর "বাঁ আগে, ডান পরে" ক্রম হুবহু মিলিয়ে recurse; এই মিল না থাকলে গঠন এলোমেলো হয়।

17. Output walkthrough

build_tree([1,2,3,None,None,4,5]) থেকে serialize দেয় "1,2,#,#,3,4,#,#,5,#,#" — assert pass। সেই string deserialize করে আবার মূল tree (round-trip same_tree pass)। খালি tree দেয় "#" → None, একক node আর [1,2] round-trip ঠিক, ঋণাত্মক value-ও টেকে — সব pass। শেষে print: সব test pass!।

18. Time complexity

O(n) দুই দিকেই — serialize প্রতিটা node (আর প্রতিটা None-প্রান্ত) একবার লেখে; deserialize প্রতিটা token একবার পড়ে node বানায়। token-সংখ্যা node-সংখ্যার রৈখিক গুণিতক (প্রতিটা None একটা marker)।

19. Space complexity

O(n) — serialize-এর output string আর token list O(n); recursion call stack tree-র height পর্যন্ত (skewed হলে O(n), balanced O(log n))। deserialize-এও একই — token list O(n) + height-সমান stack।

20. Common mistakes

  • None marker বাদ দেওয়া — তখন preorder ambiguous, deserialize গঠন ফেরাতে পারে না।
  • serialize "বাঁ আগে" কিন্তু deserialize "ডান আগে" পড়া (বা উল্টো) — ক্রম না মিললে tree আয়না-উল্টে যায়।
  • ঋণাত্মক value বা multi-digit value-কে marker #-এর সাথে গুলিয়ে ফেলা — তাই সংখ্যা আর marker আলাদা token (কমা-বিভক্ত) রাখা ভালো।
  • deserialize-এ index-counter ভুল manage করা — iterator/deque ব্যবহার করলে এই ভুল এড়ানো যায়।

21. Which basic problem this inherits from

ভিত্তি: traversal-patterns.md-র preorder, আর Construct-from-preorder-and-inorder (#21)-এর "একটা traversal থেকে tree গড়া"। পার্থক্য — এখানে inorder লাগে না, কারণ None marker-ই preorder-কে অদ্বিতীয় করে দেয়, তাই একটা traversal-ই যথেষ্ট।

22. Similar harder problems

23. Pattern learned

Marker-augmented preorder round-trip: serialize-এ preorder DFS চালাও, ফাঁকা child-এ একটা None marker লেখো; deserialize-এ একই ক্রমে token খেয়ে গাছ গড়ো (marker → None, value → node + বাঁ + ডান)। গঠনসহ tree-কে string-এ-string-থেকে আনার সব problem-এর কঙ্কাল এটাই।

24. Final summary

ভবিষ্যতের আমাকে: "tree ↔ string = marker-সহ preorder; serialize লেখে, deserialize একই ক্রমে token খেয়ে গাছ ফেরায়।" None marker আর serialize/deserialize-এর হুবহু এক ক্রম — এই দুটোই মূল। 'গঠনসহ tree সংরক্ষণ/পুনরুদ্ধার' টাইপ problem দেখলেই এই marker-preorder চালটা মনে করবে।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function buildTree(values) {
  if (!values || values.length === 0) return null;
  const root = new TreeNode(values[0]);
  const q = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const node = q[head++];
    if (i < values.length && values[i] !== null) { node.left = new TreeNode(values[i]); q.push(node.left); }
    i++;
    if (i < values.length && values[i] !== null) { node.right = new TreeNode(values[i]); q.push(node.right); }
    i++;
  }
  return root;
}

function serialize(root) {
  const out = [];
  const dfs = (node) => {
    if (node === null) { out.push("#"); return; }   // None marker
    out.push(String(node.val));                       // preorder: value আগে
    dfs(node.left);                                   // তারপর বাঁ
    dfs(node.right);                                  // তারপর ডান
  };
  dfs(root);
  return out.join(",");
}

function deserialize(data) {
  const tokens = data.split(",");
  let idx = 0;                                        // একই preorder ক্রমে পড়ার pointer
  const build = () => {
    const val = tokens[idx++];
    if (val === "#") return null;                     // None marker → ফাঁকা
    const node = new TreeNode(Number(val));
    node.left = build();                              // serialize-এর মতোই বাঁ আগে
    node.right = build();                             // তারপর ডান
    return node;
  };
  return build();
}

// round-trip যাচাইয়ের helper: দুই tree হুবহু এক কি না
function sameTree(a, b) {
  if (a === null && b === null) return true;
  if (a === null || b === null || a.val !== b.val) return false;
  return sameTree(a.left, b.left) && sameTree(a.right, b.right);
}

// ---- test cases ----
const t = buildTree([1, 2, 3, null, null, 4, 5]);
assert(serialize(t) === "1,2,#,#,3,4,#,#,5,#,#", "serialize string");
assert(sameTree(deserialize(serialize(t)), t), "round-trip");
assert(serialize(buildTree([])) === "#", "খালি tree");
assert(deserialize("#") === null, "deserialize #");
assert(sameTree(deserialize(serialize(buildTree([1]))), buildTree([1])), "একক node");
const neg = buildTree([-7, -3, 9]);
assert(sameTree(deserialize(serialize(neg)), neg), "ঋণাত্মক value");
console.log("সব JS test pass!");

JS টীকা: Python-এর iter() + next()-এর সমতুল্য এখানে একটা plain idx counter দিয়ে token-গুলো পরপর খাওয়া — যেহেতু serialize আর deserialize একই preorder ক্রমে চলে, এই চলন্ত index নিজে থেকেই সঠিক জায়গায় থাকে। Number(val) string token-কে আবার সংখ্যায় ফেরায় (ঋণাত্মক/multi-digit সহ); marker # আর সংখ্যা আলাদা token হওয়ায় গুলিয়ে যায় না।

26. TypeScript solution (with test cases)

interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }

function node(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
  return { val, left, right };
}

function buildTree(values: (number | null)[]): TreeNode | null {
  if (values.length === 0) return null;
  const root = node(values[0] as number);
  const q: TreeNode[] = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const cur = q[head++];
    if (i < values.length && values[i] !== null) { cur.left = node(values[i] as number); q.push(cur.left); }
    i++;
    if (i < values.length && values[i] !== null) { cur.right = node(values[i] as number); q.push(cur.right); }
    i++;
  }
  return root;
}

function serialize(root: TreeNode | null): string {
  const out: string[] = [];
  const dfs = (n: TreeNode | null): void => {
    if (n === null) { out.push("#"); return; }
    out.push(String(n.val));
    dfs(n.left);
    dfs(n.right);
  };
  dfs(root);
  return out.join(",");
}

function deserialize(data: string): TreeNode | null {
  const tokens = data.split(",");
  let idx = 0;
  const build = (): TreeNode | null => {
    const val = tokens[idx++];
    if (val === "#") return null;
    const cur = node(Number(val));
    cur.left = build();
    cur.right = build();
    return cur;
  };
  return build();
}

function sameTree(a: TreeNode | null, b: TreeNode | null): boolean {
  if (a === null && b === null) return true;
  if (a === null || b === null || a.val !== b.val) return false;
  return sameTree(a.left, b.left) && sameTree(a.right, b.right);
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };

const t = buildTree([1, 2, 3, null, null, 4, 5]);
expect(serialize(t) === "1,2,#,#,3,4,#,#,5,#,#", "serialize");
expect(sameTree(deserialize(serialize(t)), t), "round-trip");
expect(serialize(buildTree([])) === "#", "খালি");
expect(deserialize("#") === null, "null");
const neg = buildTree([-7, -3, 9]);
expect(sameTree(deserialize(serialize(neg)), neg), "neg");
console.log("সব TS test pass!");

TS টীকা: serialize-এর return type string আর deserialize-এর TreeNode | null — এই signature জোড়া round-trip চুক্তিটা type-এই লিখে রাখে: tree → string → tree। build-এর return type TreeNode | null বাধ্য করে marker-case (null) সামলাতে। string[] ও String(...) নিশ্চিত করে token সবসময় string, তাই Number(val) দিয়ে নিরাপদে আবার সংখ্যায় ফেরানো যায়।

27. কোথায় কাজে লাগে (real-world use)

  • Caching / persistence: একটা in-memory tree (যেমন parsed config বা index) ডিস্কে save করে পরে হুবহু restore করা — serialize/deserialize-ই এর ভিত্তি।
  • Network transmission: একটা tree structure এক সার্ভার থেকে আরেক সার্ভারে পাঠাতে string/byte-stream-এ encode করা (এই problem JSON/protobuf-এর সরলীকৃত রূপ)।
  • Undo/redo snapshots: একটা document tree-র অবস্থা serialize করে রেখে পরে সেই snapshot-এ ফেরা।
  • Inter-process / clipboard copy: একটা hierarchical data structure এক প্রসেস থেকে আরেক প্রসেসে কপি করতে flatten করা ও আবার গড়া।
  • Test fixtures / golden files: একটা পরিচিত tree serialize করে golden string হিসেবে রাখা, পরে regression test-এ মিলিয়ে দেখা।

মূল সুর: গঠনসহ কোনো tree-কে সংরক্ষণ বা পাঠাতে হলে marker-augmented preorder দিয়ে এক ক্রমে লিখে, একই ক্রমে পড়ে নিখুঁত round-trip পাওয়া যায়।

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