014 — Binary Tree Level Order Traversal¶

Problem link ও উৎস

Original source: Classic BFS tree-traversal exercise
Platform: LeetCode — https://leetcode.com/problems/binary-tree-level-order-traversal/
Topic: queue (BFS, layered)
Difficulty: Medium
Pattern: BFS (queue), layered
Basic idea inherited from: queue-র layer guarantee + len-snapshot trick; tree-traversal-এর পূর্ণ তত্ত্ব ../../09-graphs/-এ

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

তোমাকে একটা binary tree-র root দেওয়া আছে। তুমি প্রতিটা level-এর node-গুলোর value আলাদা list হিসেবে বের করবে — উপর থেকে নিচে, প্রতিটা level-এ বাঁ থেকে ডানে। উত্তরটা list-এর একটা list।

উদাহরণ

      3
     / \
    9  20
       / \
      15  7
-> [[3], [9, 20], [15, 7]]

Input ও output¶

উদাহরণ

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              -> []

চেনা উদাহরণে বোঝা¶

একটা পরিবারের বংশলতিকা (family tree) ভাবো। তুমি আগে দাদা-দাদির প্রজন্ম, তারপর বাবা-চাচার প্রজন্ম, তারপর ভাই-বোনের প্রজন্ম — এক প্রজন্ম পুরো পড়ে তবেই পরের প্রজন্মে নামো। প্রতিটা প্রজন্ম = এক level; আর "এই প্রজন্মে এখন ঠিক কতজন" সেটা জেনে নিয়ে তাদের সবার সন্তানদের পরের সারিতে দাঁড় করানোটাই len-snapshot trick।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা 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/-এ।

ভেতরের যুক্তি¶

লুকানো 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 প্রস্তুত।

কী দিয়ে তথ্য রাখব¶

একটা queue (collections.deque) যাতে node-রা থাকে। সাথে একটা result list (প্রতিটা level-এর list এতে জমবে) আর প্রতি iteration-এ একটা সাময়িক level list। tree-র node গুলো একটা সাধারণ TreeNode class দিয়ে গড়া (val, left, right)।

এটি কেন উপযুক্ত¶

level-order মানে "যে node আগে দেখেছি, তার children আগে দেখব" — হুবহু FIFO, তাই queue। stack দিয়ে বদলালে পেতে DFS, যা level গুলো এলোমেলো করে দিত। deque-এর append/popleft দুটোই O(1), আর len-snapshot trick কোনো বাড়তি marker (যেমন None দিয়ে level আলাদা করা) ছাড়াই পরিষ্কারভাবে level আলাদা করে।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

সরল চিন্তা: আগে tree-র উচ্চতা বের করো; তারপর প্রতিটা depth d-এর জন্য (0 থেকে height-1) আলাদা করে tree-তে নেমে শুধু depth d-এর node গুলো কুড়িয়ে আনো; প্রতিটা depth-এর জন্য একবার করে পুরো tree ঘোরো।

উদাহরণ

for d in range(height):
    collect_nodes_at_depth(root, d)   # প্রতিবার root থেকে নতুন করে নামা

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা depth-এর জন্য আলাদা করে root থেকে নামা মানে উপরের level-গুলো বারবার ঘোরা হয়। height h-এর tree-তে এটা প্রায় O(n × h) — skewed (একপাশে হেলানো) tree-তে h ≈ n, তাই O(n^2)। একটা মাত্র BFS-এ প্রতিটা node ঠিক একবার ছুঁয়ে সব level একবারে পাওয়া যায় — O(n)।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: iteration শুরুর সময় queue-তে যা আছে, তা ঠিক এক পুরো level — কারণ FIFO পরের level-এর কাউকে এখনো সামনে আসতে দেয়নি। তাই len(queue) snapshot নিলেই ওই level-এর সঠিক সংখ্যা মেলে; বাড়তি কোনো marker লাগে না।

আরও কম কাজে সমাধান¶

root দিয়ে queue শুরু করো (root না থাকলে খালি list ফেরাও)। queue খালি না হওয়া পর্যন্ত: একটা নতুন level list খোলো, size = len(queue) ধরো, ঠিক size বার popleft করো — প্রতিটা node-এর value level-এ দাও আর তার বিদ্যমান children queue-তে enqueue করো। loop শেষে level-টা result-এ যোগ করো। queue খালি হলে result-ই উত্তর।

ভাবনার পরিবর্তন¶

মোচড়: queue-টাকে শুধু "জমিয়ে রাখার বাক্স" না ভেবে ভাবো "এটা সবসময় ঠিক বর্তমান প্রজন্মটা ধরে আছে"। তাই প্রতিবার শুরুতে শুধু গুনে নাও কতজন আছে (len), সেই কজনকেই সামলাও — তাদের সন্তানরা যোগ হয়ে আপনাআপনি পরের প্রজন্ম গড়ে তোলে।

ছবিতে বোঝা¶

উপরের tree-তে queue level-by-level কীভাবে চলে (front বাঁয়ে):

উদাহরণ

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-এ ধাপে ধাপে¶

Input tree: root 1, left 2, right 3; 2-এর left 4; 3-এর right 5:

queue = [1], result = []
loop: size = 1; pop 1 → level=[1]; enqueue 2,3 → queue=[2,3]; result=[[1]]
loop: size = 2; pop 2 → level=[2], enqueue 4; pop 3 → level=[2,3], enqueue 5 → queue=[4,5]; result=[[1],[2,3]]
loop: size = 2; pop 4 → level=[4] (child নেই); pop 5 → level=[4,5] (child নেই) → queue=[]; result=[[1],[2,3],[4,5]]
queue খালি → return [[1],[2,3],[4,5]]

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n) — প্রতিটা node ঠিক একবার enqueue আর একবার dequeue হয়; n = tree-র মোট node সংখ্যা।

অতিরিক্ত জায়গা¶

O(n) — queue সবচেয়ে খারাপ ক্ষেত্রে সবচেয়ে চওড়া level ধরে রাখে, যা পূর্ণ binary tree-তে প্রায় n/2 node হতে পারে; result list-ও সব value ধরে।

যে ভুলগুলো এড়াতে হবে¶

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।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: queue-র FIFO discipline (BFS frontier), Problem 12/13-এর মতোই; এখানে নতুন হলো len-snapshot দিয়ে level আলাদা করা। chapter-এর ../patterns.md-এর Pattern 2 (BFS Frontier); tree/graph traversal-এর পূর্ণ আলোচনা ../../09-graphs/-এ।

পরের অনুশীলন¶

Binary Tree Zigzag Level Order Traversal — https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
Binary Tree Right Side View — https://leetcode.com/problems/binary-tree-right-side-view/
Average of Levels in Binary Tree — https://leetcode.com/problems/average-of-levels-in-binary-tree/

কৌশলটি মনে রাখুন¶

Layered BFS with len-snapshot: tree বা graph-এ "level-by-level", "প্রতিটা সারি আলাদা", "right side view" দেখলে queue চালাও আর প্রতি iteration-এ len(queue) ধরে ঠিক এক level process করো।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: BFS + প্রতি iteration-এর শুরুতে size = len(queue) ধরে ঠিক ততগুলো pop করলেই এক level আলাদা হয়। FIFO-ই level গুলো mix হতে দেয় না। "level order", "by level", "layer" দেখলে এই len-snapshot trick মনে করবে; গভীরতর traversal তত্ত্ব ../../09-graphs/।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।