5.1 Tree Traversal (DFS / BFS)
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন
Demo: Binary Tree Zigzag Level Order Traversal — LC 103 (Medium — Amazon/Meta High)
Statement (Demo): Given the root of a binary tree, return its node values in zigzag level order (first level left→right, the next right→left, and so on).
Example: root=[3,9,20,null,null,15,7] → [[3],[20,9],[15,7]] | ⚡ n ≤ 2000
Approach: Plain level-by-level BFS; just flip a direction flag on every level — even levels as they are, odd levels reversed.
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(know the iterative version too — with a stack)
Statement: Given the
rootof a binary tree, return the inorder traversal (left → root → right) of its values.
Example:root=[1,null,2,3]→[1,3,2]| ⚡n ≤ 100নোট · ফাঁকা
- Binary Tree Level Order Traversalplan · দিন ০১১LC 102
Statement: Given the
rootof a binary tree, return its values level by level, left to right, as a 2D array.
Example:root=[3,9,20,null,null,15,7]→[[3],[9,20],[15,7]]| ⚡n ≤ 2000নোট · ফাঁকা
- Serialize and Deserialize Binary TreeLC 297(Hard — Google/Meta High; preorder + null marker is simplest)
Statement: Design an algorithm to serialize a binary tree to a string and deserialize the string back to the same tree. The format is up to you.
Example:root=[1,2,3,null,null,4,5]→ serialize → deserialize → same tree | ⚡n ≤ 10⁴নোট · ফাঁকা
- Maximum Depth of Binary Treeplan · দিন ০০৮LC 104(the "hello world" of recursion)
Statement: Given the
rootof a binary tree, return its maximum depth — the number of nodes on the longest root-to-leaf path.
Example:root=[3,9,20,null,null,15,7]→3| ⚡n ≤ 10⁴নোট · ফাঁকা