012 — Binary Tree Level Order Traversal¶
Source¶
- Original source: Classic breadth-first tree traversal exercise
- Platform: LeetCode — https://leetcode.com/problems/binary-tree-level-order-traversal/
- Topic: trees
- Difficulty: Medium
- Pattern: Level order (queue)
- Basic idea inherited from:
../../04-stack-and-queue/-এর queue — FIFO order layer-এর পর layer খালি করে
1. Problem in simple words¶
তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: node-গুলোর value level ধরে ধরে ফেরত দেওয়া — প্রথমে root-এর level, তারপর তার নিচের level, এভাবে। প্রতিটা level আলাদা একটা list, আর পুরোটা একটা list-of-lists।
একই level-এর মধ্যে বাঁ থেকে ডানে order রাখতে হবে।
2. Which basic idea does this inherit from?¶
এটা সরাসরি ../../04-stack-and-queue/-র 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:
প্রতিটা 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 হয় না।
6. Real-life analogy¶
একটা building-এ আগুন লেগেছে, তুমি floor ধরে ধরে খালি করছ। আগে পুরো ground floor-এর সবাইকে বের করো, তারপর first floor, তারপর second। একটা floor সম্পূর্ণ খালি না হলে পরের floor-এ যাও না। Queue হলো তোমার "এর পরে কাকে ডাকব" লাইন; floor-এর সীমানা হলো len(q) snapshot।
7. Visual explanation¶
প্রতিটা wave queue-তে কী থাকে তা দেখাচ্ছে; size দিয়ে আমরা ঠিক সেই wave-টুকু কাটি:
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]]
8. Example input and output¶
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]]
9. Brute force thinking¶
প্রথম সরল চিন্তা: প্রতিটা node-এর depth আলাদা করে বের করি (recursion দিয়ে), তারপর depth ধরে group করি।
1) DFS দিয়ে প্রতিটা (node.val, depth) জোড়া জমাও
2) depth-key-এ একটা dict বানাও: depth → [values]
3) depth 0, 1, 2... 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-গুলোকে পরিষ্কার ভাগ করে দেয়।
14. Step-by-step dry run¶
Input [3,9,20,null,null,15,7]:
q = [3]।size = 1→ 3 তোলো, level[3], enqueue 9, 20।q = [9, 20]।size = 2→ 9 তোলো (child নেই), 20 তোলো (enqueue 15, 7)। level[9, 20]।q = [15, 7]।size = 2→ 15 তোলো, 7 তোলো (কারো child নেই)। level[15, 7]।q = []।- queue খালি → শেষ।
result = [[3], [9, 20], [15, 7]]।
15. Python solution¶
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-এ যোগ করো।
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!।
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 সহ) ফেরত দেওয়া, যেখানে সঠিক উত্তর[]।
21. Which basic problem this inherits from¶
ভিত্তি: ../../04-stack-and-queue/-এর queue আর traversal-patterns.md-র level-order snippet। ওই size = len(q) কায়দাটা এখানকার সব level-ভিত্তিক problem-এর মূল।
22. Similar harder problems¶
- Binary Tree Right Side View (প্রতি level-এর শেষ node রাখো) — https://leetcode.com/problems/binary-tree-right-side-view/ (এই tracker-এর #13)
- Binary Tree Zigzag Level Order Traversal (alternate level উল্টে দাও) — https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
- Average of Levels in Binary Tree (প্রতি level-এর গড়) — https://leetcode.com/problems/average-of-levels-in-binary-tree/
23. Pattern learned¶
Level-snapshot BFS: queue দিয়ে BFS করো, কিন্তু প্রতিটা layer process করার আগে size = len(q) snapshot নাও। এই একটা লাইন সব "per-level" problem-এর কঙ্কাল — right side view, zigzag, level average, level width — সবই এই snapshot-এর উপর দাঁড়ায়।
24. Final summary¶
ভবিষ্যতের আমাকে: "level order = queue + size = len(q) snapshot।" যখনই কোনো problem level/layer/depth ধরে কিছু চায়, এই BFS কঙ্কালটা মনে করবে — Level Order Traversal হলো তার সবচেয়ে পরিষ্কার রূপ, আর বাকি সব per-level problem এর উপর একটা ছোট মোচড় মাত্র।
25. JavaScript solution (with test cases)¶
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-দের একটা আলাদাnextarray-তে জমিয়ে, তারপরq = nextদিয়ে পরের level-এ লাফ। এতেshift()-এর O(n) খরচ এড়ানো যায় আর level-সীমা স্বাভাবিকভাবেই বজায় থাকে। nested array তুলনায়JSON.stringifyদরকার।
26. TypeScript solution (with test cases)¶
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 হওয়ায় ভুল করেnullpush করা আটকায়, তাইfor...of-এর ভেতরেcur.valছোঁয়া নিরাপদ (extra null-check ছাড়াই)।nextarray-ও typed, যাতে frontier-এ শুধু আসল node থাকে।
27. কোথায় কাজে লাগে (real-world use)¶
- UI tree rendering depth-wise: একটা component/menu tree-কে স্তরে স্তরে render বা animate করা (যেমন একটা একটা level fade-in করা)।
- Org chart / hierarchy display: কোনো প্রতিষ্ঠানের কাঠামো স্তর ধরে দেখানো — CEO level, তারপর VP level, এভাবে।
- Shortest path in unweighted graph: BFS level-order-ই unweighted graph-এ source থেকে দূরত্ব দেয় (প্রতিটা level = এক hop দূরের সব node)।
- Network broadcast / flood: একটা node থেকে সব প্রতিবেশীতে wave আকারে message ছড়ানো — কোন round-এ কে পৌঁছাল তা track করা।
- Web crawler depth limit: একটা page থেকে link ধরে BFS করে নির্দিষ্ট depth পর্যন্ত page crawl করা (level = link-দূরত্ব)।
মূল সুর: "স্তর/দূরত্ব ধরে কিছু process করো" দেখলেই queue-ভিত্তিক level-order BFS-এর কথা ভাববে — right-side view, zigzag, level average সবই এর উপর ছোট মোচড়।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।