Algorithm-Day42-Binary-Tree-Level-Order-Traversal-lc-102

Posted on In , Views:

🧩 Problem Description

Given the root of a binary tree, return the level order traversal of its nodes’ values (i.e., from left to right, level by level).

💬 Example

1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

💡 Approach: Breadth-First Search (BFS)

This is a classic BFS traversal problem using a queue:

  1. Start from the root and process each level of the tree.
  2. For each node in the current level, push its children into the queue.
  3. Collect all node values level by level.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            res.add(level);
        }

        return res;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — every node is visited once
  • Space Complexity: O(n) — queue + output list

✍️ Summary

  • Straightforward BFS template.
  • Common interview question to test level-by-level traversal.
  • Often used in problems involving:
    • Tree depth
    • Zigzag/spiral level order
    • Node connect (next pointers)

Try implementing variations like lc-107, lc-103, lc-199.