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) as a 2D array.

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

Output: [[3],[9,20],[15,7]]

Level 0: [3], Level 1: [9,20], Level 2: [15,7].

Input: root = [1]

Output: [[1]]

Single node.

Time

O(n)

each node enqueued/dequeued once.

Space

O(n)

queue holds up to n/2 nodes at leaf level.

#1 Standard tree

Input: [3,9,20,null,null,15,7]

Expected: [[3],[9,20],[15,7]]

#2 Single node

Input: [1]

Expected: [[1]]

#3 Empty tree

Input: []

Expected: []

#4 Five-node tree

Input: [1,2,3,4,5]

Expected: [[1],[2,3],[4,5]]