Topic 66 of 79

Level Order

Q: How would you print the 'Right View' of a Binary Tree? (The nodes visible if you look at the tree from the right side).

Use Level Order Traversal. The inner loop processes a specific level. The very last element processed in that inner loop (when `i == levelSize - 1`) is guaranteed to be the rightmost node of that level. Simply add only that specific node to your result list.

Q: What is the Space Complexity of Tree BFS?

O(W), where W is the maximum width of the tree. In a perfectly balanced binary tree, the bottom level holds exactly half of all nodes (N/2). Therefore, the queue will simultaneously hold N/2 nodes, making the worst-case space complexity O(N).

Overview

Level Order Traversal is simply Breadth-First Search (BFS) applied to a Binary Tree.

Instead of traversing a tree by going as deep as possible down one branch (DFS), a Level Order Traversal reads the tree exactly how you would read a book: left to right, top to bottom. It prints the root (Level 0), then the root's left and right children (Level 1), then all four of their children (Level 2).

The implementation is nearly identical to Graph BFS (it relies entirely on a Queue). However, it is fundamentally simpler because trees, by strict mathematical definition, do not have cycles (loops) and all child edges point strictly downwards. Therefore, a 'Visited Set' is entirely unnecessary when doing Level Order Traversal on a valid tree.

Syntax

Tree Level Order Traversal

java

import java.util.*;

public class TreeBFS {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // LeetCode Classic: Return a list of lists, where each sublist represents a level
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result; // Always handle null root safely
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // Lock in the size of the current level
            List<Integer> currentLevelData = new ArrayList<>();
            
            // Process ONLY the nodes that were present at the start of this level
            for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                currentLevelData.add(current.val);
                
                // Add children for the NEXT level (Notice: No Visited Set needed!)
                if (current.left != null) queue.offer(current.left);
                if (current.right != null) queue.offer(current.right);
            }
            
            result.add(currentLevelData); // Store the completed level
        }
        
        return result;
    }
}

Common Pitfalls

Adding null to the queue. Always explicitly check if (node.left != null) before enqueuing. If you blindly enqueue nulls, queue.poll() will eventually return null, and your next line current.val will instantly trigger a NullPointerException.
Forgetting to capture queue.size() before the inner loop. If you write for(int i=0; i < queue.size(); i++), the size of the queue is actively changing as you enqueue children. The loop will run far longer than the current level. You MUST store int size = queue.size(); before the loop starts.
Overcomplicating with a visited set. In a standard tree structure, child nodes never point back to their parents, so you can never enter an infinite loop. Using a HashSet here wastes memory and CPU cycles.

Interview Questions

How would you print the 'Right View' of a Binary Tree? (The nodes visible if you look at the tree from the right side).

Use Level Order Traversal. The inner loop processes a specific level. The very last element processed in that inner loop (when i == levelSize - 1) is guaranteed to be the rightmost node of that level. Simply add only that specific node to your result list.

What is the Space Complexity of Tree BFS?

O(W), where W is the maximum width of the tree. In a perfectly balanced binary tree, the bottom level holds exactly half of all nodes (N/2). Therefore, the queue will simultaneously hold N/2 nodes, making the worst-case space complexity O(N).

Real-World Example

Serialization of a Tree data structure for network transmission. If you need to send a complex binary tree across a REST API, you flatten it into a JSON array using Level Order Traversal (often replacing missing children with 'null' strings). This format allows the receiving client to instantly rebuild the exact tree structure by reading the array sequentially left-to-right.

example

java

import java.util.*;

class TreeNode { int val; TreeNode left, right; }

public class TreeSerializer {
    // Outputting a tree into a flat string format: "[1,2,3,null,null,4,5]"
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            TreeNode curr = q.poll();
            
            if (curr == null) {
                sb.append("null,");
            } else {
                sb.append(curr.val).append(",");
                // We enqueue nulls here intentionally to map the empty spaces
                q.offer(curr.left); 
                q.offer(curr.right);
            }
        }
        
        // Cleanup trailing commas and add bracket
        sb.deleteCharAt(sb.length() - 1); 
        return sb.toString() + "]";
    }
}

Check Your Knowledge

Test your understanding of Level Order with these quick questions.

What is the main difference in implementation between Tree BFS and Graph BFS?

Why is capturing `int size = queue.size();` crucial before iterating through a level?

In the worst-case scenario (a perfectly balanced tree), how much auxiliary memory does the Queue require?

Take Java Quiz

Overview

Level Order Traversal is simply Breadth-First Search (BFS) applied to a Binary Tree.

Syntax

Tree Level Order Traversal

java

import java.util.*;

public class TreeBFS {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // LeetCode Classic: Return a list of lists, where each sublist represents a level
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result; // Always handle null root safely
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // Lock in the size of the current level
            List<Integer> currentLevelData = new ArrayList<>();
            
            // Process ONLY the nodes that were present at the start of this level
            for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                currentLevelData.add(current.val);
                
                // Add children for the NEXT level (Notice: No Visited Set needed!)
                if (current.left != null) queue.offer(current.left);
                if (current.right != null) queue.offer(current.right);
            }
            
            result.add(currentLevelData); // Store the completed level
        }
        
        return result;
    }
}

Common Pitfalls

Adding null to the queue. Always explicitly check if (node.left != null) before enqueuing. If you blindly enqueue nulls, queue.poll() will eventually return null, and your next line current.val will instantly trigger a NullPointerException.
Forgetting to capture queue.size() before the inner loop. If you write for(int i=0; i < queue.size(); i++), the size of the queue is actively changing as you enqueue children. The loop will run far longer than the current level. You MUST store int size = queue.size(); before the loop starts.
Overcomplicating with a visited set. In a standard tree structure, child nodes never point back to their parents, so you can never enter an infinite loop. Using a HashSet here wastes memory and CPU cycles.

Interview Questions

How would you print the 'Right View' of a Binary Tree? (The nodes visible if you look at the tree from the right side).

What is the Space Complexity of Tree BFS?

Real-World Example

example

java

import java.util.*;

class TreeNode { int val; TreeNode left, right; }

public class TreeSerializer {
    // Outputting a tree into a flat string format: "[1,2,3,null,null,4,5]"
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        
        while (!q.isEmpty()) {
            TreeNode curr = q.poll();
            
            if (curr == null) {
                sb.append("null,");
            } else {
                sb.append(curr.val).append(",");
                // We enqueue nulls here intentionally to map the empty spaces
                q.offer(curr.left); 
                q.offer(curr.right);
            }
        }
        
        // Cleanup trailing commas and add bracket
        sb.deleteCharAt(sb.length() - 1); 
        return sb.toString() + "]";
    }
}

Check Your Knowledge

Test your understanding of Level Order with these quick questions.