algoadvance

Leetcode 102. Binary Tree Level Order Traversal

Problem Statement

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).

Clarifying Questions

  1. Q: What is the expected input and output format?
    • A: The input is the root node of a binary tree, and the output should be a list of lists, where each inner list contains the values of the tree nodes at each level.
  2. Q: Can the tree be empty?
    • A: Yes, the tree can be empty. In such a case, the function should return an empty list.
  3. Q: Are there any constraints on the values of the nodes?
    • A: There are no specific constraints mentioned, but typically binary tree nodes will have integer values.
  4. Q: How large can the tree be?
    • A: The size of the tree (the number of nodes) is not specified, but the solution should be efficient enough to handle large trees.

Strategy

To solve the problem of level order traversal in a binary tree, we can use the Breadth-First Search (BFS) technique. BFS traverses the tree level by level, making it ideal for this task. We will use a queue to help with the traversal:

  1. Initialization: Check if the tree is empty; if yes, return an empty list. Otherwise, initialize a queue with the root node.
  2. Traversal: While the queue is not empty, process nodes level by level:
    • Get the number of nodes at the current level.
    • Dequeue nodes one by one, adding their values to the current level list.
    • Enqueue the child nodes of the dequeued nodes.
  3. Compilation: After processing all levels, compile the values into a result list and return it.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

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.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);
                
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            
            result.add(currentLevel);
        }
        
        return result;
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI