## Problem Given a binary tree, return its values in level order as a list of lists. Values at depth `0` appear in the first list, values at depth `1` in the second, and so on. Preserve left-to-right order within each level. ### Function Contract Implement `levelOrder(root)`. ### Constraints & Assumptions - The tree contains at most `100,000` nodes. - Node values are signed 32-bit integers and may repeat. - Return an empty list for an empty tree. ### Clarifying Questions to Ask - Is a flat breadth-first list sufficient? No, group values by depth. - Must left-to-right order be preserved? Yes. - Can the tree be skewed? Yes. - May the input contain shared or cyclic child references? No, it is a valid tree. ```hint Freeze the current breadth At the start of each breadth-first iteration, record the queue size; exactly that many nodes belong to the current level. ``` ### Example ```text tree = [3, 9, 20, null, null, 15, 7] output = [[3], [9, 20], [15, 7]] ``` ### Evaluation Focus - Groups nodes at the correct depth. - Preserves child order and handles missing children. - Avoids repeated list shifting with an inefficient queue representation. - Runs in `O(n)` time and uses `O(w)` queue space for maximum width `w`. ### Extensions to Discuss 1. How would you stream one completed level at a time? 2. How would zigzag level order change the collection step? 3. What is the worst-case queue size for a balanced tree?