Problem link ও উৎস
- **Original source:** Classic "turn a tree into a string and back" exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Hard
- **Pattern:** Preorder construction
- **Basic idea inherited from:** Preorder + None markers
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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 করতে হবে।
```text
1 serialize → "1,2,3,#,#,4,5,#,#,#,#"
/ \ (# = None marker, preorder ক্রমে)
2 3
/ \
4 5 deserialize → ঠিক এই tree-ই ফিরিয়ে আনে
```
### Input ও output {#8-example-input-and-output}
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা পরিবার-গাছ ফোনে কাউকে মুখে বলে দিচ্ছ। তুমি বলবে: "আগে নিজের নাম, তারপর বাঁ সন্তানের পুরো শাখা, তারপর ডান সন্তানের পুরো শাখা। যেখানে কেউ নেই, সেখানে বলবে 'খালি'।" ওপ্রান্তের লোক ঠিক একই ক্রমে শুনে শুনে কাগজে গাছটা আঁকবে — 'খালি' শুনলে সেদিকে কিছু আঁকবে না। 'খালি' শব্দটাই (marker) নিশ্চিত করে দু'জনের আঁকা গাছ হুবহু এক হবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এর **অদ্বিতীয়তা**:
```text
serialize(node):
node None হলে → "#" লেখো
নইলে → node.val লেখো, তারপর serialize(left), তারপর serialize(right)
deserialize(tokens): # একই preorder ক্রমে পড়ো
পরের token নাও
"#" হলে → None ফেরত
নইলে → node বানাও, node.left = deserialize(tokens), node.right = deserialize(tokens)
```
মূল বুদ্ধি: 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 সেই ফাঁক বন্ধ করে গঠন অদ্বিতীয় করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা — marker ছাড়া: শুধু preorder value-গুলো জমাই, আর deserialize-এ অনুমান করি কোথায় ভাঙব।
```text
1) serialize: শুধু value preorder-এ লেখো → "1,2,3,4,5"
2) deserialize: প্রথমটা root; বাকি values-এর কোনগুলো বাঁ, কোনগুলো ডান তা জানা নেই।
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-এর চেয়ে এখানে সহজ)।
### ছবিতে বোঝা {#7-visual-explanation}
preorder ক্রমে value আর `#` (None) লেখা হয়; deserialize সেই tokens একই ক্রমে খায়:
```text
1
/ \
2 3
/ \
4 5
preorder tokens: 1 2 # # 3 4 # # 5 # #
↑root ↑2-leaf ↑3 ↑4-leaf ↑5-leaf
```
### ছোট input-এ ধাপে ধাপে {#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।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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 বানায় (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; এই মিল না থাকলে গঠন এলোমেলো হয়।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
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 হওয়ায় গুলিয়ে যায় না।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
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)` দিয়ে নিরাপদে আবার সংখ্যায় ফেরানো যায়।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 ব্যবহার করলে এই ভুল এড়ানো যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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}
- Construct Binary Tree from Preorder and Inorder (marker ছাড়া দুই traversal দিয়ে গঠন) —