Practice/Meta/Leetcode 102. Binary Tree Level Order Traversal

Leetcode 102. Binary Tree Level Order Traversal

CodingMust

Problem

Given the root of a binary tree, return a list of lists containing the node values organized by their depth level. Each inner list should contain all node values at that particular depth, ordered from left to right. If the tree is empty, return an empty list.

This traversal pattern visits all nodes at depth 0, then all nodes at depth 1, and so on, processing nodes at each level from left to right before moving to the next level.

Requirements

1. Return a 2D array where each inner array represents one level of the tree
2. Nodes within each level must be ordered from left to right
3. Process levels in order from root (depth 0) to leaves
4. Handle the empty tree case by returning an empty list

Constraints

• The number of nodes in the tree is in the range [0, 2000]
• -1000 ≤ Node.val ≤ 1000
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(w) where w is the maximum width of the tree

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 Output: [[3], [9, 20], [15, 7]] Explanation: The root forms the first level, its children form the second level, and the leaf nodes form the third level.

Example 2:

Input: root = [1] Output: [[1]] Explanation: A single node tree has only one level.

Example 3:

Input: root = [] Output: [] Explanation: An empty tree has no levels to traverse.

Example 4:

Input: root = [1,2,3,4,5,6,7] 1 / \ 2 3 / \ / \ 4 5 6 7 Output: [[1], [2, 3], [4, 5, 6, 7]] Explanation: Three levels with increasing number of nodes per level.