5.1 Tree Traversal (DFS / BFS)

চিনবেন কীভাবে

"visit all nodes", "level order", "zigzag", "inorder/preorder/postorder", serialize — traversal order-ই প্রশ্নের প্রাণ

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Binary Tree Zigzag Level Order Traversal — LC 103 (Medium — Amazon/Meta High)

Statement (Demo): binary tree-এর root দেওয়া — nodes-এর মান zigzag level order-এ return করুন (প্রথম level বাম→ডান, দ্বিতীয় level ডান→বাম, এভাবে চলতে থাকবে)। উদাহরণ: root=[3,9,20,null,null,15,7] → [[3],[20,9],[15,7]] | ⚡ n ≤ 2000

Approach: সাধারণ BFS level-by-level, শুধু প্রতি level-এ direction flag উল্টে দিন — জোড় level সোজা, বিজোড় উল্টো।

function zigzagLevelOrder(root) {
  if (!root) return [];
  const res = [];
  let queue = [root],
    leftToRight = true;
  while (queue.length) {
    const level = queue.map((n) => n.val);
    res.push(leftToRight ? level : level.reverse());
    queue = queue.flatMap((n) => [n.left, n.right].filter(Boolean));
    leftToRight = !leftToRight;
  }
  return res;
}

Complexity: Time O(n), Space O(n)

প্রবলেম

Binary Tree Inorder TraversalLC 94
(iterative-টাও পারতে হবে — stack দিয়ে)
Statement: binary tree-এর root দেওয়া — inorder traversal (left → root → right) এ nodes-এর value-গুলো array হিসেবে return করুন।
উদাহরণ: root=[1,null,2,3] → [1,3,2] | ⚡ n ≤ 100
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Binary Tree Level Order Traversalplan · দিন ০৩১ LC 102
Statement: binary tree-এর root দেওয়া — nodes-এর মান level order-এ (level-by-level, বাম থেকে ডান) 2D array হিসেবে return করুন।
উদাহরণ: root=[3,9,20,null,null,15,7] → [[3],[9,20],[15,7]] | ⚡ n ≤ 2000
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Serialize and Deserialize Binary TreeLC 297
(Hard — Google/Meta High; preorder + null marker সবচেয়ে সহজ)
Statement: binary tree serialize করার (string-এ convert) এবং deserialize করার (string থেকে tree reconstruct) algorithm design করুন। format আপনার নিজের।
উদাহরণ: root=[1,2,3,null,null,4,5] → serialize → deserialize → same tree | ⚡ n ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Maximum Depth of Binary Treeplan · দিন ০২৫ LC 104
(recursion-এর hello world)
Statement: binary tree-এর root দেওয়া — root node থেকে সবচেয়ে দূরের leaf node পর্যন্ত সর্বোচ্চ গভীরতা (number of nodes along the longest path) বের করুন।
উদাহরণ: root=[3,9,20,null,null,15,7] → 3 | ⚡ n ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন