Binary Tree Level Order Traversal medium

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

Example 1

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

Example 2

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

Steps

1. Initialization: Create an empty list result to store the level order traversal. Initialize a queue queue with the root node.

2. Level-by-Level Traversal: While the queue is not empty:

   • Get the size levelSize of the queue. This represents the number of nodes at the current level.
   • Create an empty list levelNodes to store the values of nodes at the current level.
   • Iterate levelSize times:
     • Dequeue a node from the queue.
     • Add the node's value to levelNodes.
     • If the node has a left child, enqueue the left child.
     • If the node has a right child, enqueue the right child.
   • Add levelNodes to result.

3. Return: Return result.

Explanation

The algorithm uses a Breadth-First Search (BFS) approach to traverse the binary tree level by level. The queue acts as a buffer, holding nodes that need to be processed. By getting the size of the queue before processing each level, we ensure that we process all nodes at the current level before moving to the next. This guarantees the level order traversal.

Code

import java.util.*;

public class BinaryTreeLevelOrderTraversal {
    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> levelNodes = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelNodes.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(levelNodes);
        }

        return result;
    }

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

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst-case scenario (a complete binary tree), W can be equal to N, but in general, it will be less than N. The space complexity is dominated by the queue which holds nodes at each level.