Return a Binary Tree in Level Order

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.

Example

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?