Problem link ও উৎস
- **Original source:** Classic "rebuild the tree from two traversals" exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Construction
- **Basic idea inherited from:** Preorder = top-down + inorder split (hash index, [../../05-hashing/](../../05-hashing/README.md) থেকে)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একই tree-র দুটো traversal দেওয়া আছে — একটা **preorder** (Node → Left → Right) আর একটা **inorder** (Left → Node → Right)। দুটো list-এ একই value-গুলো আছে, শুধু ক্রম আলাদা। তোমার কাজ: এই দুটো থেকে আসল binary tree-টা আবার বানানো (root node ফেরত দেওয়া)।
ধরে নাও tree-তে কোনো value-র **পুনরাবৃত্তি নেই** (LeetCode তাই বলে) — না হলে কোন value কোনটা সেটা আলাদা করা যেত না।
```text
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7] → এই tree বানাও:
3
/ \
9 20
/ \
15 7
```
### Input ও output {#8-example-input-and-output}
```text
Input : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: tree → level-order [3,9,20,null,null,15,7]
Input : preorder = [1,2], inorder = [2,1] -> tree: 1 with left child 2
Input : preorder = [1,2], inorder = [1,2] -> tree: 1 with right child 2
Edge : preorder = [], inorder = [] -> None (খালি tree)
Edge : preorder = [42], inorder = [42] -> একটামাত্র node 42
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা মিছিলের দুটো রিপোর্ট আছে। একটায় (preorder) লেখা "আগে নেতা, তারপর তাঁর পুরো বাঁ দল, তারপর পুরো ডান দল"। আরেকটায় (inorder) সবাই বাঁ-থেকে-ডান দাঁড়ানোর ক্রমে আছে — মাঝখানে নেতা। তুমি preorder থেকে জানো নেতা কে; inorder-এ নেতাকে খুঁজে পেলেই বুঝে যাও তাঁর বাঁ পাশে কারা, ডান পাশে কারা। প্রতিটা উপ-দলে আবার একই কৌশল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত্তি একসাথে। প্রথমত **preorder-এর গঠন**: তার একদম প্রথম element সবসময় বর্তমান subtree-র **root**। দ্বিতীয়ত **inorder-এর split-ক্ষমতা**: ওই root-কে inorder-এ খুঁজে পেলে তার বাঁ পাশের সব value = বাঁ subtree, ডান পাশের সব = ডান subtree। আর সেই root-কে দ্রুত খুঁজতে আমরা [../../05-hashing/](../../05-hashing/README.md)-এর hash map (value → inorder index) ব্যবহার করি।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা recursive split:
```text
1) preorder-এর পরের value = বর্তমান subtree-র root
2) inorder-এ সেই root-এর index = mid
3) inorder[left..mid-1] = বাঁ subtree (আকার = mid - left)
inorder[mid+1..right] = ডান subtree
4) preorder-এ root-এর ঠিক পরে বাঁ subtree-র সব value, তারপর ডানের সব
5) বাঁ আগে গড়ো (preorder বাঁ আগে খায়), তারপর ডান — recurse
```
মূল গণিত: preorder যে ক্রমে node "জন্ম" দেয় (root আগে, তারপর পুরো বাঁ, তারপর পুরো ডান), inorder সেই অনুসারে left/right-এ ভাগ করে দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
তিনটে জিনিস: ইনপুট দুটো **list** (preorder, inorder), একটা **hash map** (`value → inorder index`, যাতে root খোঁজা O(1)), আর **recursion call stack**। আর একটা চলন্ত pointer `pre_idx` — preorder-এ আমরা কতদূর এগিয়েছি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিবার root খুঁজতে inorder পুরো scan করলে O(n²) হয়ে যায়। **hash map** value-কে সরাসরি inorder index-এ map করে দেয়, তাই root খোঁজা O(1) — এখানেই [../../05-hashing/](../../05-hashing/README.md)-এর শিক্ষা কাজে লাগে। **recursion** tree-র self-similar গঠনে নিখুঁত খাপ খায়: প্রতিটা subtree আবার একই preorder-root + inorder-split নিয়মে গড়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা — hash map ছাড়া: প্রতিবার preorder-এর সামনের value নাও (root), তারপর সেটা **inorder-এ linear scan** করে খুঁজে index বের করো, বাঁ/ডান slice বানিয়ে recurse করো।
```text
1) root = preorder[0] = 3
2) inorder-এ 3 খোঁজো (scan) → index 1
3) বাঁ inorder = [9], ডান inorder = [15,20,7]
4) দুই পাশে আবার একই কাজ (প্রতিবার scan + নতুন slice)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো খরচ জমে। (১) প্রতিটা node-এ inorder পুরো **scan** করা — n বার scan, প্রতিটা O(n) পর্যন্ত → **O(n²)**। (২) প্রতিবার `preorder[1:]`, `inorder[:mid]` ইত্যাদি **নতুন slice** বানানো — extra memory আর copy। দুটোই সরানো যায়: scan-এর জায়গায় hash map (O(1) lookup), আর slice-এর জায়গায় index-range `(lo, hi)` পাস করা।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation দুটো: **(১) preorder-এর প্রথম element সবসময় বর্তমান subtree-র root।** **(২) inorder-এ সেই root তার বাঁ আর ডান subtree-কে দুই ভাগে কেটে দেয়।** এই দুটো একসাথে মানে — প্রতিটা subtree-র জন্য আমরা ঠিক জানি কোন value-গুলো বাঁয়ে আর কোনগুলো ডানে যাবে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা চলন্ত `pre_idx` রাখো (preorder-এ পরবর্তী root কোথায়)। একটা helper `build(lo, hi)` inorder-এর `[lo, hi]` অংশ গড়ে: `preorder[pre_idx]` থেকে root নাও, `pre_idx` এগোও, hash map থেকে root-এর inorder index `mid` পাও, তারপর **আগে `build(lo, mid-1)`** (বাঁ), **তারপর `build(mid+1, hi)`** (ডান)। বাঁ আগে কারণ preorder root-এর পরেই পুরো বাঁ subtree রাখে। পুরো tree একবার গড়া হয় → O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** list slice করা বন্ধ করো — তার বদলে **index range** নিয়ে কাজ করো, আর preorder-এ একটা ভাগ করা pointer (`pre_idx`) রাখো যেটা একই ক্রমে এগোয়। আর সবচেয়ে জরুরি ক্রম: **বাঁ subtree আগে গড়ো**, কারণ preorder root-এর ঠিক পরেই বাঁ-এর সব value রাখে; ডান আগে গড়লে `pre_idx` ভুল value তুলে আনবে।
### ছবিতে বোঝা {#7-visual-explanation}
preorder প্রথমে 3 দেয় (root); inorder-এ 3-এর বাঁয়ে `[9]`, ডানে `[15,20,7]`:
```text
preorder: [3 | 9 | 20 15 7] 3 = root
inorder: [9 | 3 | 15 20 7] 9 = বাঁ subtree, [15,20,7] = ডান subtree
3
/ \
বাঁ → 9 20 ←(পরের root, ডান অংশের preorder থেকে)
/ \
15 7
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`preorder = [3,9,20,15,7]`, `inorder = [9,3,15,20,7]`, `idx = {9:0, 3:1, 15:2, 20:3, 7:4}`:
1. `pre_idx=0`, `build(0,4)`: root = 3 (`pre_idx`→1), mid = idx[3] = 1। বাঁ = `build(0,0)`, ডান = `build(2,4)`।
2. `build(0,0)`: root = 9 (`pre_idx`→2), mid = 0। বাঁ = `build(0,-1)` = None, ডান = `build(1,0)` = None → leaf 9।
3. `build(2,4)`: root = 20 (`pre_idx`→3), mid = idx[20] = 3। বাঁ = `build(2,2)`, ডান = `build(4,4)`।
4. `build(2,2)`: root = 15 (`pre_idx`→4) → leaf 15। `build(4,4)`: root = 7 (`pre_idx`→5) → leaf 7।
5. গঠন: 3 → (9, 20), 20 → (15, 7)। ঠিক target 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 level_order(root):
"""tree → trailing-None-ছাঁটা level-order list (যাচাইয়ের জন্য)।"""
if root is None:
return []
out, q = [], deque([root])
while q:
node = q.popleft()
if node is None:
out.append(None)
continue
out.append(node.val)
q.append(node.left)
q.append(node.right)
while out and out[-1] is None: # লেজের None ছেঁটে দাও
out.pop()
return out
def build_from_pre_in(preorder, inorder):
idx = {val: i for i, val in enumerate(inorder)} # value → inorder index
pre_idx = 0
def build(lo, hi):
nonlocal pre_idx
if lo > hi: # খালি range → কোনো node নেই
return None
root_val = preorder[pre_idx] # preorder-এর পরের value = root
pre_idx += 1
node = TreeNode(root_val)
mid = idx[root_val] # inorder-এ root কোথায় (O(1))
node.left = build(lo, mid - 1) # বাঁ আগে (preorder বাঁ আগে রাখে)
node.right = build(mid + 1, hi) # তারপর ডান
return node
return build(0, len(inorder) - 1)
# ---- tests ----
t1 = build_from_pre_in([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
assert level_order(t1) == [3, 9, 20, None, None, 15, 7]
t2 = build_from_pre_in([1, 2], [2, 1])
assert level_order(t2) == [1, 2] # 2 হলো বাঁ child
t3 = build_from_pre_in([1, 2], [1, 2])
assert level_order(t3) == [1, None, 2] # 2 হলো ডান child
assert level_order(build_from_pre_in([], [])) == [] # খালি tree
assert level_order(build_from_pre_in([42], [42])) == [42] # একক node
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `idx = {val: i ...}` — value → inorder index map; root-কে inorder-এ O(1)-তে খুঁজতে।
- `pre_idx = 0` — preorder-এ পরবর্তী root-এর pointer; `nonlocal` দিয়ে সব recursive call একই pointer ভাগ করে।
- `if lo > hi: return None` — base case: inorder-এর খালি range মানে এই দিকে কোনো node নেই।
- `root_val = preorder[pre_idx]; pre_idx += 1` — বর্তমান subtree-র root নাও আর pointer এগোও।
- `mid = idx[root_val]` — inorder-এ root-এর অবস্থান; বাঁ/ডান কোথায় ভাগ হবে তা ঠিক করে।
- `node.left = build(lo, mid - 1)` — **আগে বাঁ**, কারণ preorder root-এর পরেই বাঁ subtree রাখে।
- `node.right = build(mid + 1, hi)` — তারপর ডান; এই ক্রম না মানলে `pre_idx` ভুল value তুলবে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build_from_pre_in([3,9,20,15,7], [9,3,15,20,7])` ওই ছবির tree বানায়; `level_order` `[3,9,20,None,None,15,7]` দেয় — assert pass। `[1,2]`/`[2,1]` দেয় বাঁ child 2 (`[1,2]`), `[1,2]`/`[1,2]` দেয় ডান child 2 (`[1,None,2]`), খালি দেয় `[]`, একক node দেয় `[42]` — সব pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার তৈরি হয়, আর hash map-এর কল্যাণে প্রতিটা root-lookup O(1)। map বানাতে শুরুতে O(n)। (linear-scan version হতো O(n²)।)
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — hash map-এ n entry, plus recursion call stack tree-র height পর্যন্ত (skewed হলে O(n), balanced হলে O(log n))। output tree নিজেও O(n), যা অনিবার্য।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- **ডান subtree আগে গড়া** — `pre_idx` যেহেতু ভাগ করা ও preorder বাঁ আগে রাখে, ডান আগে গড়লে value-গুলো এলোমেলো হয়ে যাবে।
- প্রতিবার list **slice** করা (`preorder[1:]`) — কাজ করে কিন্তু O(n²) আর বাড়তি memory; index-range পাস করাই ভালো।
- inorder index খুঁজতে প্রতিবার `inorder.index(root)` ডাকা — সেটাই O(n²) করে দেয়; hash map লাগবে।
- duplicate value থাকলে এই পদ্ধতি ভাঙে — কোন copy কোনটা তা inorder-এ অদ্বিতীয়ভাবে বলা যায় না (problem তাই unique ধরে)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: traversal-patterns.md-র preorder/inorder সংজ্ঞা (preorder root আগে দেয়, inorder root-এ মাঝে থাকে) আর [../../05-hashing/](../../05-hashing/README.md)-এর value→index map। দুটো এক হলে — "preorder থেকে root, inorder থেকে split" — পুরো construction দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Construct Binary Tree from Inorder and Postorder (postorder root **শেষে** দেয়, তাই ডান আগে গড়ো) —