Binary Tree Level Order Traversal

Solutions

Breadth-First Search (BFS)

Time: O(N)Space: O(N)

This solution uses a queue to perform a breadth-first search (BFS) traversal of the binary tree. It starts by adding the root node to the queue. Then, it enters a loop that continues until the queue is empty. In each iteration, it processes all nodes at the current level by removing them from the queue, adding their values to the current level, and adding their children to the queue. Once all nodes at the current level have been processed, it adds the current level to the result and repeats the process for the next level.

import java.util.Queue;

import java.util.LinkedList;


public
class Solution {
  
  
  public List<List<Integer>> levelOrder(TreeNode root) {
    
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    
    queue.add(root);
    
    while (!queue.isEmpty()) {
      
      List<Integer> level = new ArrayList<>();
      
      int levelSize = queue.size();
      
      for (int i = 0;
      i < levelSize;
      i++) {
        
        TreeNode node = queue.poll();
        
        level.add(node.val);
        
        if (node.left != null) queue.add(node.left);
        
        if (node.right != null) queue.add(node.right);
        
      }
      
      result.add(level);
      
    }
    
    return result;
    
  }
  
}

Constraints:

Examples:

Solutions

Breadth-First Search (BFS)

Follow-up: