Binary Tree Level Order Traversal II

Given the root of a binary tree, return its level order traversal, but with each level collected into a separate list. This problem is a variation of the standard level order traversal and is useful for analyzing tree structure at different depths, such as identifying patterns or calculating statistics for each level.

Problem Description

You are given the root node of a binary tree. Your task is to perform a level order traversal of the tree and return a list of lists, where each inner list represents a level of the tree. The elements within each inner list should be the values of the nodes at that level, ordered from left to right.

What needs to be achieved:

• Traverse the binary tree level by level.
• Collect the node values at each level into a separate list.
• Return a list containing these level-specific lists.

Key Requirements:

• The traversal should be performed in breadth-first order (level by level).
• The order of nodes within each level's list should be left to right.
• Handle empty trees gracefully.

Expected Behavior:

The function should return an empty list if the input tree is empty (root is null). Otherwise, it should return a list of lists, where each inner list contains the node values at a specific level.

Edge Cases to Consider:

• Empty tree (root is null).
• Tree with only one node.
• Unbalanced trees (trees where the left and right subtrees have significantly different depths).
• Trees with varying node values.

Examples

Example 1:

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

(Visual representation: 3 /
9 20 /
15 7 )

Output: [[3],[9,20],[15,7]]
Explanation: The tree has three levels. The first level contains only 3. The second level contains 9 and 20. The third level contains 15 and 7.

Example 2:

Input: root = [1]

(Visual representation: 1 )

Output: [[1]]
Explanation: The tree has one level, containing only the node with value 1.

Example 3:

Input: root = [] (empty tree)

Output: []
Explanation: An empty tree should return an empty list.

Constraints

• The number of nodes in the tree will be in the range [0, 1000].
• The values of the nodes will be integers.
• The solution should have a time complexity of O(N), where N is the number of nodes in the tree.
• The solution should have a space complexity of O(W), where W is the maximum width of the tree (maximum number of nodes at any level).

Notes

Consider using a queue to perform the level order traversal. Each time you dequeue a node, add its value to the current level's list. When the queue is empty, start a new level's list and enqueue the children of the nodes processed in the previous level. Remember to handle null children appropriately.