Binary Tree Level Order Traversal DSA Solution - Study Chapter | QuizMaker

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 6: Trees

Learning Outcome

After this lesson, you should be able to use a queue to group binary tree nodes level by level.

Problem Statement

Given the root of a binary tree, return the level order traversal of its node values. Each level should be grouped in its own list.

Brute Force Approach

Run DFS separately for each depth and collect nodes at that depth.

This can revisit nodes many times. BFS gives each level directly in one traversal.

Optimized Approach

Use a queue. At the start of each level, record the current queue size. Pop exactly that many nodes to build one level, then push their children for the next level.

Exact Pseudocode

if root is null:
  return []
queue = [root]
answer = []
while queue is not empty:
  size = queue.length
  level = []
  repeat size times:
    node = queue.pop_front()
    level.add(node.val)
    if node.left exists: queue.push_back(node.left)
    if node.right exists: queue.push_back(node.right)
  answer.add(level)
return answer

Reference Code

from collections import deque

class Solution:
    def levelOrder(self, root):
        if not root:
            return []

        queue = deque([root])
        answer = []

        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            answer.append(level)

        return answer

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return {};

        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> answer;

        while (!q.empty()) {
            int size = q.size();
            vector<int> level;

            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            answer.push_back(level);
        }

        return answer;
    }
};

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> answer = new ArrayList<>();
        if (root == null) return answer;

        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);
            }

            answer.add(level);
        }

        return answer;
    }
}

Sample Dry Run

Complexity

Edge Cases

• Empty tree returns an empty list.
• Single-node tree returns one level.
• Do not let newly added children affect the current level's loop count.

Interview Checklist

• Snapshot queue size before processing a level.
• Pop exactly that many nodes.
• Add children for the next level only.

FAQs

BFS naturally visits nodes level by level, which matches the output format.

It separates the current level from children added for the next level.

BFS with a queue.

Tags

• dsa
• trees
• bfs queue