Problem link ও উৎস
- **Original source:** Classic BFS tree-traversal exercise
- **Platform:** LeetCode —
- **Topic:** queue (BFS, layered)
- **Difficulty:** Medium
- **Pattern:** BFS (queue), layered
- **Basic idea inherited from:** queue-র layer guarantee + `len`-snapshot trick; tree-traversal-এর পূর্ণ তত্ত্ব [../../09-graphs/](../../09-graphs/README.md)-এ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree-র root দেওয়া আছে। তুমি প্রতিটা level-এর node-গুলোর value আলাদা list হিসেবে বের করবে — উপর থেকে নিচে, প্রতিটা level-এ বাঁ থেকে ডানে। উত্তরটা list-এর একটা list।
```text
3
/ \
9 20
/ \
15 7
-> [[3], [9, 20], [15, 7]]
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [3,9,20,null,null,15,7] -> Output: [[3],[9,20],[15,7]]
Input : root = [1] -> Output: [[1]]
Input : root = [] -> Output: []
Edge case 1 (একপাশে হেলানো): 1->2->3 (সব left) -> [[1],[2],[3]]
Edge case 2 (root শুধু) : [1] -> [[1]]
Edge case 3 (খালি tree) : None -> []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা পরিবারের বংশলতিকা (family tree) ভাবো। তুমি আগে দাদা-দাদির প্রজন্ম, তারপর বাবা-চাচার প্রজন্ম, তারপর ভাই-বোনের প্রজন্ম — এক প্রজন্ম পুরো পড়ে তবেই পরের প্রজন্মে নামো। প্রতিটা প্রজন্ম = এক level; আর "এই প্রজন্মে এখন ঠিক কতজন" সেটা জেনে নিয়ে তাদের সবার সন্তানদের পরের সারিতে দাঁড় করানোটাই `len`-snapshot trick।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **BFS (queue)** pattern, এখানে tree-র উপর। আগের দুটো (Number of Islands, Rotting Oranges) যেমন grid-এ ring-by-ring ছড়াত, এখানে আমরা tree-তে level-by-level নামি। মূল নতুন কৌশল হলো **`len`-snapshot trick** — প্রতিটা iteration-এর শুরুতে `len(queue)` ধরে নিয়ে ঠিক ততগুলো node process করা, যাতে একেকটা level আলাদা করে কুড়িয়ে নেওয়া যায়। tree/graph traversal-এর পূর্ণ আলোচনা [../../09-graphs/](../../09-graphs/README.md)-এ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: queue-র FIFO order নিশ্চিত করে level-d-এর সব node level-(d+1)-এর যেকোনো node-এর **আগে** dequeue হয়। তাই যেকোনো মুহূর্তে queue হয় পুরোপুরি এক level ধরে রাখে, নয় দুটো পাশাপাশি level-এর অংশ। iteration শুরুর `len(queue)` snapshot ঠিক বর্তমান level-এর node-সংখ্যা — কারণ পরের level-এর কেউ এখনো যোগ হয়নি। ওই কয়টা pop করে children push করলেই এক level সাফ, পরের level প্রস্তুত।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **queue** (`collections.deque`) যাতে node-রা থাকে। সাথে একটা `result` list (প্রতিটা level-এর list এতে জমবে) আর প্রতি iteration-এ একটা সাময়িক `level` list। tree-র node গুলো একটা সাধারণ `TreeNode` class দিয়ে গড়া (val, left, right)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
level-order মানে "যে node আগে দেখেছি, তার children আগে দেখব" — হুবহু FIFO, তাই queue। stack দিয়ে বদলালে পেতে DFS, যা level গুলো এলোমেলো করে দিত। `deque`-এর `append`/`popleft` দুটোই O(1), আর `len`-snapshot trick কোনো বাড়তি marker (যেমন `None` দিয়ে level আলাদা করা) ছাড়াই পরিষ্কারভাবে level আলাদা করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: আগে tree-র উচ্চতা বের করো; তারপর প্রতিটা depth `d`-এর জন্য (0 থেকে height-1) আলাদা করে tree-তে নেমে শুধু depth `d`-এর node গুলো কুড়িয়ে আনো; প্রতিটা depth-এর জন্য একবার করে পুরো tree ঘোরো।
```text
for d in range(height):
collect_nodes_at_depth(root, d) # প্রতিবার root থেকে নতুন করে নামা
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা depth-এর জন্য আলাদা করে root থেকে নামা মানে উপরের level-গুলো বারবার ঘোরা হয়। height `h`-এর tree-তে এটা প্রায় **O(n × h)** — skewed (একপাশে হেলানো) tree-তে `h ≈ n`, তাই O(n^2)। একটা মাত্র BFS-এ প্রতিটা node ঠিক একবার ছুঁয়ে সব level একবারে পাওয়া যায় — O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: iteration শুরুর সময় queue-তে যা আছে, তা ঠিক **এক পুরো level** — কারণ FIFO পরের level-এর কাউকে এখনো সামনে আসতে দেয়নি। তাই `len(queue)` snapshot নিলেই ওই level-এর সঠিক সংখ্যা মেলে; বাড়তি কোনো marker লাগে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
root দিয়ে queue শুরু করো (root না থাকলে খালি list ফেরাও)। queue খালি না হওয়া পর্যন্ত: একটা নতুন `level` list খোলো, `size = len(queue)` ধরো, ঠিক `size` বার popleft করো — প্রতিটা node-এর value `level`-এ দাও আর তার বিদ্যমান children queue-তে enqueue করো। loop শেষে `level`-টা `result`-এ যোগ করো। queue খালি হলে `result`-ই উত্তর।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** queue-টাকে শুধু "জমিয়ে রাখার বাক্স" না ভেবে ভাবো "এটা সবসময় ঠিক বর্তমান প্রজন্মটা ধরে আছে"। তাই প্রতিবার শুরুতে শুধু গুনে নাও কতজন আছে (`len`), সেই কজনকেই সামলাও — তাদের সন্তানরা যোগ হয়ে আপনাআপনি পরের প্রজন্ম গড়ে তোলে।
### ছবিতে বোঝা {#7-visual-explanation}
উপরের tree-তে queue level-by-level কীভাবে চলে (front বাঁয়ে):
```text
init: queue=[3]
level loop #1: size=len(queue)=1
pop 3 -> level=[3]; children 9,20 enqueue queue=[9,20]
result=[[3]]
level loop #2: size=2
pop 9 -> level=[9]; 9-র child নেই
pop 20 -> level=[9,20]; children 15,7 enqueue queue=[15,7]
result=[[3],[9,20]]
level loop #3: size=2
pop 15 -> level=[15]; child নেই
pop 7 -> level=[15,7]; child নেই queue=[]
result=[[3],[9,20],[15,7]]
queue খালি -> থামো
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input tree: root `1`, left `2`, right `3`; `2`-এর left `4`; `3`-এর right `5`:
1. `queue = [1]`, `result = []`
2. loop: `size = 1`; pop `1` → `level=[1]`; enqueue `2`,`3` → `queue=[2,3]`; `result=[[1]]`
3. loop: `size = 2`; pop `2` → `level=[2]`, enqueue `4`; pop `3` → `level=[2,3]`, enqueue `5` → `queue=[4,5]`; `result=[[1],[2,3]]`
4. loop: `size = 2`; pop `4` → `level=[4]` (child নেই); pop `5` → `level=[4,5]` (child নেই) → `queue=[]`; `result=[[1],[2,3],[4,5]]`
5. queue খালি → return `[[1],[2,3],[4,5]]`
## কোড ও ব্যাখ্যা {#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):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)): # len-snapshot: এই level-এর সংখ্যা
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# ---- tests ----
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
assert level_order(root) == [[3], [9, 20], [15, 7]]
assert level_order(TreeNode(1)) == [[1]] # root শুধু
assert level_order(None) == [] # খালি tree
# একপাশে হেলানো: 1 -> 2 -> 3 (সব left)
skew = TreeNode(1, TreeNode(2, TreeNode(3)))
assert level_order(skew) == [[1], [2], [3]]
# 1: left 2(left 4), right 3(right 5)
mixed = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, None, TreeNode(5)))
assert level_order(mixed) == [[1], [2, 3], [4, 5]]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `class TreeNode` — সাধারণ binary-tree node: `val`, `left`, `right`।
- `if not root: return []` — খালি tree-তে কোনো level নেই।
- `queue = deque([root])` — BFS root দিয়ে শুরু।
- `for _ in range(len(queue)):` — মূল কৌশল; iteration-এর শুরুতে queue-তে ঠিক বর্তমান level-এর node থাকে, তাই এই গণনা সঠিক।
- `node = queue.popleft()` / `level.append(node.val)` — FIFO order-এ pop, value কুড়াও।
- `if node.left: ... if node.right:` — থাকা children পরের level-এর জন্য enqueue।
- `result.append(level)` — এক level সম্পূর্ণ হলে result-এ যোগ।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`level_order(root)` (root 3) → section 7-এর trace মতো `[[3],[9,20],[15,7]]`। `level_order(skew)` → প্রতিটা level-এ একটিমাত্র node, তাই `[[1],[2],[3]]`। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার enqueue আর একবার dequeue হয়; `n` = tree-র মোট node সংখ্যা।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — queue সবচেয়ে খারাপ ক্ষেত্রে সবচেয়ে চওড়া level ধরে রাখে, যা পূর্ণ binary tree-তে প্রায় `n/2` node হতে পারে; result list-ও সব value ধরে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `len(queue)` snapshot আগে না নিয়ে loop-এর ভেতরেই `len(queue)` চেক করা — তখন এই level-এ যোগ-হওয়া children-ও একই level-এ ঢুকে level mix হয়ে যায়।
- root `None` কিনা শুরুতে না দেখা — `deque([None])` দিলে পরে `node.val`-এ error।
- child push করার আগে অস্তিত্ব (`if node.left`) না দেখা — `None` queue-তে ঢুকে গেলে crash।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: queue-র FIFO discipline (BFS frontier), Problem 12/13-এর মতোই; এখানে নতুন হলো `len`-snapshot দিয়ে level আলাদা করা। chapter-এর [../patterns.md](../patterns.md)-এর Pattern 2 (BFS Frontier); tree/graph traversal-এর পূর্ণ আলোচনা [../../09-graphs/](../../09-graphs/README.md)-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Binary Tree Zigzag Level Order Traversal —