Problem link ও উৎস
- **Original source:** Classic breadth-first tree traversal exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** Level order (queue)
- **Basic idea inherited from:** [../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-এর queue — FIFO order layer-এর পর layer খালি করে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: node-গুলোর value **level ধরে ধরে** ফেরত দেওয়া — প্রথমে root-এর level, তারপর তার নিচের level, এভাবে। প্রতিটা level আলাদা একটা list, আর পুরোটা একটা list-of-lists।
একই level-এর মধ্যে বাঁ থেকে ডানে order রাখতে হবে।
```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]]
Edge : root = [] -> Output: [] (খালি tree)
Input : root = [1,2,3,4,null,null,5]
Output: [[1], [2, 3], [4, 5]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা building-এ আগুন লেগেছে, তুমি floor ধরে ধরে খালি করছ। আগে পুরো ground floor-এর সবাইকে বের করো, তারপর first floor, তারপর second। একটা floor সম্পূর্ণ খালি না হলে পরের floor-এ যাও না। Queue হলো তোমার "এর পরে কাকে ডাকব" লাইন; floor-এর সীমানা হলো `len(q)` snapshot।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি [../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-র **queue** থেকে আসে। Stack (LIFO) দিলে depth-first ঘোরা হতো; কিন্তু এখানে আমরা চাই কাছের জিনিস আগে — তাই **FIFO queue**। Node enqueue করো, সামনে থেকে নাও, তার child পেছনে দাও। এই "আগে এসেছে আগে বেরোবে" নিয়মই layer-এর সীমানা ধরে রাখে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **BFS by distance from root**:
```text
level 0 = {root}
level (k+1) = level k-এর সব node-এর children
```
প্রতিটা node-এর level = root থেকে তার দূরত্ব। Queue-তে যখন একটা level-এর সব node থাকে, তখন `len(q)` ঠিক সেই level-এর size — এই snapshot নিয়ে exactly একটা layer process করা যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **FIFO queue** — Python-এ `collections.deque`, যেটা দুই প্রান্তেই O(1)। আমরা সামনে থেকে `popleft()` করি আর পেছনে `append()` করি। সাথে output জমাতে list-of-lists।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Queue-র FIFO ধর্ম নিশ্চিত করে যে একটা level-এর সব node তাদের child-এর আগে process হয়। `deque` এজন্যই perfect: `list.pop(0)` O(n) হতো (সবাইকে সরাতে হয়), কিন্তু `deque.popleft()` O(1)। তাই বড় tree-তেও queue কখনো bottleneck হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা node-এর depth আলাদা করে বের করি (recursion দিয়ে), তারপর depth ধরে group করি।
```text
1) DFS দিয়ে প্রতিটা (node.val, depth) জোড়া জমাও
2) depth-key-এ একটা dict বানাও: depth → [values]
3) depth-এর ছোট থেকে বড় order-এ dict থেকে list বের করো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা আসলে কাজ করে আর O(n)-ও থাকে, কিন্তু দুই-pass: একবার সব জমানো, আরেকবার depth ধরে সাজানো। আর order রক্ষা করতে সাবধান থাকতে হয় (DFS বাঁ-আগে গেলে left-to-right ঠিক থাকে, কিন্তু এটা সহজে ভুল হয়)। BFS এক pass-এই natural left-to-right level order দেয় — পরিষ্কার আর কম bug-প্রবণ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **queue-তে যখন এক level-এর সব node থাকে, তখন `len(q)` ঠিক সেই level-এর সংখ্যা।** তাই process শুরুর আগে size snapshot নিয়ে, ঠিক ততবার `popleft` করলেই একটা পুরো level আলাদা হয়ে যায় — পরের level-এর enqueue হওয়া node-গুলো এই গোনায় ঢোকে না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
এটা **level order** traversal (BFS): queue দিয়ে layer-by-layer। প্রতিটা iteration-এর শুরুতে `size = len(q)` নাও, ঠিক `size` বার loop করে এই level-এর node তোলো ও তাদের value জমাও, আর child-দের পরের level-এর জন্য enqueue করো। প্রতিটা node ঠিক একবার enqueue/dequeue হয় — O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো tree একসাথে ঘুরব" ভাবা বন্ধ করো। বরং ভাবো "এক wave করে এগোব, আর প্রতিটা wave শুরুর আগে তার আকার মেপে নেব।" ওই `size = len(q)` লাইনটাই recursion-এর depth-tracking ছাড়াই level-গুলোকে পরিষ্কার ভাগ করে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা wave queue-তে কী থাকে তা দেখাচ্ছে; `size` দিয়ে আমরা ঠিক সেই wave-টুকু কাটি:
```text
queue শুরু: [3] size=1 → level [3], enqueue 9, 20
queue: [9, 20] size=2 → level [9,20], enqueue 15, 7
queue: [15, 7] size=2 → level [15,7], কোনো child নেই
queue: [] → শেষ
result = [[3], [9, 20], [15, 7]]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[3,9,20,null,null,15,7]`:
1. `q = [3]`। `size = 1` → 3 তোলো, level `[3]`, enqueue 9, 20। `q = [9, 20]`।
2. `size = 2` → 9 তোলো (child নেই), 20 তোলো (enqueue 15, 7)। level `[9, 20]`। `q = [15, 7]`।
3. `size = 2` → 15 তোলো, 7 তোলো (কারো child নেই)। level `[15, 7]`। `q = []`।
4. queue খালি → শেষ। `result = [[3], [9, 20], [15, 7]]`।
## কোড ও ব্যাখ্যা {#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 level_order(root):
if root is None: # খালি tree: কোনো level নেই
return []
levels, q = [], deque([root]) # BFS queue (../../04-stack-and-queue/)
while q:
size = len(q) # এই snapshot = ঠিক একটা level
level = []
for _ in range(size):
node = q.popleft() # সামনের node (FIFO)
level.append(node.val)
if node.left:
q.append(node.left) # child পরের level-এর জন্য পেছনে
if node.right:
q.append(node.right)
levels.append(level) # পুরো level জমা হলো
return levels
# ---- tests ----
assert level_order(build_tree([3, 9, 20, None, None, 15, 7])) == [[3], [9, 20], [15, 7]]
assert level_order(build_tree([1])) == [[1]]
assert level_order(build_tree([])) == []
assert level_order(build_tree([1, 2, 3, 4, None, None, 5])) == [[1], [2, 3], [4, 5]]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if root is None: return []` — খালি tree-তে কোনো level নেই।
- `levels, q = [], deque([root])` — output list আর BFS queue, root দিয়ে শুরু।
- `size = len(q)` — মূল চাল: এই snapshot বর্তমান level-এর সীমানা ধরে রাখে।
- `for _ in range(size)` — ঠিক ততবার loop, যাতে শুধু এই level-এর node তোলা হয়।
- `node = q.popleft()` — FIFO: সামনের node নাও।
- `if node.left: q.append(...)` / `if node.right: ...` — child পরের level-এর জন্য পেছনে enqueue।
- `levels.append(level)` — পুরো level শেষ হলে output-এ যোগ করো।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build_tree([3,9,20,None,None,15,7])` ওই ছবির tree বানায়; `level_order` `[[3], [9, 20], [15, 7]]` ফেরত দেয় — assert pass। একক node দেয় `[[1]]`, খালি tree দেয় `[]`, আর shape-করা tree দেয় `[[1], [2, 3], [4, 5]]` — সব 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 levelOrder(root) {
if (root === null) return []; // খালি tree: কোনো level নেই
const levels = [];
let q = [root]; // BFS frontier (এক level)
while (q.length > 0) {
const level = [], next = [];
for (const node of q) { // q = ঠিক একটা level
level.push(node.val);
if (node.left) next.push(node.left); // child পরের level-এর জন্য
if (node.right) next.push(node.right);
}
levels.push(level);
q = next; // পরের level-এ সরো
}
return levels;
}
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// ---- test cases ----
assert(eq(levelOrder(buildTree([3, 9, 20, null, null, 15, 7])), [[3], [9, 20], [15, 7]]), "basic");
assert(eq(levelOrder(buildTree([1])), [[1]]), "একক node");
assert(eq(levelOrder(buildTree([])), []), "খালি");
assert(eq(levelOrder(buildTree([1, 2, 3, 4, null, null, 5])), [[1], [2, 3], [4, 5]]), "shaped");
console.log("সব JS test pass!");
```
> **JS টীকা:** Python-এ `size = len(q)` snapshot নিয়ে level আলাদা করা হয়; JS-এ এখানে আরও পরিষ্কার একটা কায়দা ব্যবহার করেছি — পুরো বর্তমান `q`-এর উপর `for...of` চালিয়ে child-দের একটা আলাদা `next` array-তে জমিয়ে, তারপর `q = next` দিয়ে পরের level-এ লাফ। এতে `shift()`-এর O(n) খরচ এড়ানো যায় আর level-সীমা স্বাভাবিকভাবেই বজায় থাকে। nested array তুলনায় `JSON.stringify` দরকার।
### 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 levelOrder(root: TreeNode | null): number[][] {
if (root === null) return [];
const levels: number[][] = [];
let q: TreeNode[] = [root];
while (q.length > 0) {
const level: number[] = [];
const next: TreeNode[] = [];
for (const cur of q) {
level.push(cur.val);
if (cur.left) next.push(cur.left);
if (cur.right) next.push(cur.right);
}
levels.push(level);
q = next;
}
return levels;
}
const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a: number[][], b: number[][]): boolean =>
a.length === b.length && a.every((row, i) => row.length === b[i].length && row.every((v, j) => v === b[i][j]));
expect(eq(levelOrder(buildTree([3, 9, 20, null, null, 15, 7])), [[3], [9, 20], [15, 7]]), "basic");
expect(eq(levelOrder(buildTree([1])), [[1]]), "একক");
expect(eq(levelOrder(buildTree([])), []), "খালি");
expect(eq(levelOrder(buildTree([1, 2, 3, 4, null, null, 5])), [[1], [2, 3], [4, 5]]), "shaped");
console.log("সব TS test pass!");
```
> **TS টীকা:** return type `number[][]` (array-of-arrays) স্পষ্ট করে দেয় ফলাফলের আকৃতি — list-of-lists। `q: TreeNode[]` typed হওয়ায় ভুল করে `null` push করা আটকায়, তাই `for...of`-এর ভেতরে `cur.val` ছোঁয়া নিরাপদ (extra null-check ছাড়াই)। `next` array-ও typed, যাতে frontier-এ শুধু আসল node থাকে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার enqueue আর একবার dequeue হয় (n = node সংখ্যা)। প্রতিটা value একবার output-এ যায়। এর চেয়ে কম সম্ভব না, কারণ সব value ফেরত দিতেই হবে।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — queue-তে সবচেয়ে বেশি একটা পুরো level থাকতে পারে; চওড়া tree-তে শেষ level-এ প্রায় n/2 node, তাই O(n)। Output নিজেই O(n) জায়গা নেয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `size = len(q)` snapshot না নিয়ে `while q` লুপে সরাসরি কাজ করা → সব level একসাথে মিশে যায়, level-এর সীমানা হারায়।
- `list.pop(0)` ব্যবহার করা `deque.popleft()`-এর বদলে → প্রতিটা pop O(n), মোট O(n²)।
- খালি tree-তে `[[]]` (একটা খালি level সহ) ফেরত দেওয়া, যেখানে সঠিক উত্তর `[]`।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: [../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-এর queue আর traversal-patterns.md-র level-order snippet। ওই `size = len(q)` কায়দাটা এখানকার সব level-ভিত্তিক problem-এর মূল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Binary Tree Right Side View (প্রতি level-এর শেষ node রাখো) —