8. Binary Tree Level Order Traversal

Description

Binary Tree Level Order Traversal

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:

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

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Approach

• Make sure we will return empty list for null root while in calculation we cannot add empty list
• Time: O(n) Space: O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> d = new ArrayList<>();
        if (root == null) return d;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> l = new ArrayList<>();
            for (int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                l.add(n.val);
                if(n.left != null) q.add(n.left);
                if(n.right != null) q.add(n.right);
            }
            d.add(l);
        }
        return d;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> a = new ArrayList<>();
        if (root == null) {
            return a;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            List<Integer> l = new ArrayList<>();
            for (int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                if (n != null) {
                    l.add(n.val);
                    q.add(n.left);
                    q.add(n.right);
                }
            }
            if (l.size() > 0) a.add(l);
        }
        return a;
    }
}

Approach 1: BFS Level-Order Traversal ($O(N)$ Time, $O(N)$ Space)

Intuition

Use a queue (ArrayDeque) to process the tree level by level:

1. At each iteration, capture the current queue.size() to determine how many nodes belong to the current level.
2. Poll each node, append its value to a currentLevel sublist, and push its non-null left and right children into the queue.
3. Append currentLevel to the main result list before moving to the next level.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
 
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
 
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
 
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
 
            for (int i = 0; i < levelSize; i++) {
                TreeNode curr = queue.poll();
                currentLevel.add(curr.val);
 
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
 
            result.add(currentLevel);
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node in the binary tree is processed exactly once.
• Space Complexity: $O(N)$ — The queue holds at most $N/2$ nodes at the widest level of a balanced tree.

---

Approach 2: Recursive DFS Level Tracking ($O(N)$ Time, $O(N)$ Space)

Intuition

Traverse the tree using Depth-First Search while passing down the current depth level:

1. If depth == result.size(), it indicates the first arrival at this level, so instantiate and append a new ArrayList<Integer>.
2. Add node.val to the list at index depth (result.get(depth)).
3. Recursively call dfs on node.left and node.right with depth + 1.

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }
 
    private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
        if (node == null) return;
 
        // First time reaching this level -> add a new level list
        if (depth == result.size()) {
            result.add(new ArrayList<>());
        }
 
        // Add node value to its corresponding level list
        result.get(depth).add(node.val);
 
        dfs(node.left, depth + 1, result);
        dfs(node.right, depth + 1, result);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node is visited once.
• Space Complexity: $O(N)$ worst-case call stack depth for a skewed tree ($O(\log N)$ for a balanced tree).

---

Easy Memory Rule

“BFS: Process queue.size() elements per loop $\to$ OR DFS: If depth == result.size(), create new sublist and append at depth!”