Problem link ও উৎস
- **Original source:** Classic tree traversal exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Easy
- **Pattern:** Traversal order
- **Basic idea inherited from:** Inorder, visit-মুহূর্ত সরানো — value নেওয়ার লাইন একদম উপরে তুলে দাও
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree-র root দেওয়া আছে। সব value একটা list-এ ফেরত দাও — **preorder** ক্রমে, মানে **Node → Left → Right**।
প্রতিটা node-এ: আগে নিজের value নাও, তারপর পুরো বাঁ-দিক, তারপর পুরো ডান-দিক। parent সবসময় তার সব descendant-এর আগে আসে।
```text
1
\
2
/
3 ← preorder = [1, 2, 3]
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [1,null,2,3]
Output: [1, 2, 3]
Input : root = [] -> Output: [] (খালি tree)
Input : root = [1] -> Output: [1] (একটা node)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা বইয়ের table of contents ভাবো। আগে chapter-এর শিরোনাম লেখা হয়, তারপর তার সব section, তারপর পরের chapter। তুমি একটা heading-এ পৌঁছেই সেটা লিখে ফেলো, তারপর তার ভেতরে ঢোকো। এটাই preorder — "আগে আমি, তারপর আমার ভেতরের সব।"
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **inorder**-এরই যমজ ভাই (এই tracker-এর #2)। একই recursion কঙ্কাল, শুধু value নেওয়ার লাইনটা **মাঝখান থেকে একদম উপরে** তুলে দেওয়া হয়েছে — তাই node তার child-দের আগে visit হয়। "visit-মুহূর্ত সরানো" — এটাই তিন DFS traversal-এর মধ্যে পার্থক্য।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic আবার একটা ক্রমের সংজ্ঞা:
```text
preorder(empty) = []
preorder(node) = [node.val] + preorder(node.left) + preorder(node.right)
```
এর একটা গুরুত্বপূর্ণ ধর্ম: parent সবসময় আগে লেখা হয় বলে preorder output থেকে tree-টা **top-down আবার বানানো** যায়। এজন্যই preorder হলো copy / serialize-এর স্বাভাবিক ক্রম (traversal-patterns.md দেখো)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **output list** আর **recursion call stack**। recursion-এর বদলে চাইলে একটা explicit stack ([../../04-stack-and-queue/](../../04-stack-and-queue/README.md)) — root push করো, pop করে visit করো, তারপর RIGHT তারপর LEFT push করো (যাতে left আগে pop হয়)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Tree self-similar, তাই recursion প্রতিটা subtree আলাদা সামলায়। preorder-এ আমরা node-এ পৌঁছেই (on ARRIVAL) value নিই, তাই কোনো জিনিস "মনে রেখে পরে নেওয়ার" ঝামেলা নেই — পৌঁছালাম, লিখলাম, নিচে নামলাম। stack/recursion শুধু "এরপর কোন দিক বাকি" ধরে রাখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
Traversal নিজেই কাজ, তাই brute force বলতে **iterative explicit-stack** version — recursion ছাড়া হাতে stack চালানো।
```text
1) root-কে stack-এ push করো
2) stack থেকে pop করো → value নাও
3) আগে RIGHT, তারপর LEFT push করো (যাতে left আগে pop হয়)
4) stack খালি না হওয়া পর্যন্ত ধাপ 2 চালাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
Iterative version-ও O(n), slow না — কিন্তু "right তারপর left push" উল্টো বোধ হয়, ভুল হওয়া সহজ। recursion সেই subtlety নিজেই সামলায়, code পরিষ্কার থাকে। iterative লাগে শুধু খুব গভীর tree-তে Python-এর recursion limit এড়াতে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: inorder-এর তুলনায় শুধু **একটা লাইন উপরে উঠেছে** — `append` এখন দুই recursive call-এর আগে। তাই node তার বংশধরদের আগে লেখা হয়। ক্রম বদলানো মানে শুধু এই এক লাইন সরানো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
তিন লাইনের recursion: এই node-এর value append করো, বাঁয়ে নামো, ডানে নামো। `None`-এ চুপচাপ ফিরে যাও। একবার tree ঘোরা — প্রতিটা node পৌঁছানোমাত্র লেখা হয়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "preorder মানে কী" আলাদা করে মুখস্থ না করে ভাবো — "inorder-এর append লাইনটা টেনে একদম উপরে তুলে দিলাম।" তিন traversal = একটাই কঙ্কাল, append-লাইনের তিনটা অবস্থান (উপরে / মাঝে / নিচে)।
### ছবিতে বোঝা {#7-visual-explanation}
★ মানে value নেওয়া হলো — preorder-এ সেটা node-এ পৌঁছানোমাত্রই (নিচে নামার আগে):
```text
1★
/ \
2★ 3★
/ \
4★ 5★
হাঁটা: 1★ (পৌঁছেই) → 2★ → 4★ → 5★ → 3★
preorder = [1, 2, 4, 5, 3]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[1,null,2,3]` (tree: 1-এর right 2, 2-এর left 3):
1. `visit(1)`: পৌঁছেই append `1`। out = [1]।
2. `visit(1.left = None)`: চুপচাপ ফিরল।
3. `visit(1.right = 2)`: append `2`। out = [1, 2]।
4. `visit(2.left = 3)`: append `3`। out = [1, 2, 3]। left/right None → ফিরল।
5. সব শেষ → **[1, 2, 3]**।
## কোড ও ব্যাখ্যা {#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 বানায়।"""
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 preorder_traversal(root):
out = []
def visit(node):
if node is None: # base case: খালি subtree
return
out.append(node.val) # 1) পৌঁছেই নিজের value (on ARRIVAL)
visit(node.left) # 2) তারপর পুরো বাঁ-দিক
visit(node.right) # 3) তারপর পুরো ডান-দিক
visit(root)
return out
# ---- tests ----
assert preorder_traversal(build_tree([1, None, 2, 3])) == [1, 2, 3]
assert preorder_traversal(build_tree([])) == []
assert preorder_traversal(build_tree([1])) == [1]
assert preorder_traversal(build_tree([1, 2, 3, 4, 5])) == [1, 2, 4, 5, 3]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `out = []` — value জমানোর জায়গা।
- `if node is None: return` — base case; খালি subtree থেকে কিছু যোগ হয় না।
- `out.append(node.val)` — মূল চাল: node-এ পৌঁছেই, নিচে নামার আগে value নাও।
- `visit(node.left)` / `visit(node.right)` — তারপর বাঁ, তারপর ডান।
- `return out` — পুরো preorder sequence।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,null,2,3]` → [1, 2, 3] (dry run-এর সাথে মেলে)। খালি tree → []; একক node → [1]; `[1,2,3,4,5]` → [1,2,4,5,3] (ছবির সাথে মেলে)। সব assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার visit ও append।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** output list-এর জন্য; recursion stack আলাদাভাবে **O(h)** (balanced-এ O(log n), chain-এ O(n))।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `append` লাইন নিচে রেখে ভুল করে inorder/postorder বানিয়ে ফেলা।
- iterative version-এ left আর right push-এর ক্রম উল্টে দেওয়া (right আগে push করতে হয়)।
- base case বাদ দিয়ে `None` ছোঁয়া।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Inorder Traversal (#2) — একই কঙ্কাল, append-লাইন উপরে তোলা। সাথে traversal-patterns.md-র preorder sketch, যেখানে দেখানো হয় কেন preorder = copy/serialize-এর ক্রম।
### পরের অনুশীলন {#22-similar-harder-problems}
- Construct Binary Tree from Preorder and Inorder Traversal (preorder = top-down root, inorder দিয়ে split) —