Binary Tree Level Order Traversal II (Bottom-up)

To solve the bottom-up level order traversal, I would first clarify that we need to return levels starting from the leaves up to the root. My approach involves using a standard Breadth-First Search strategy with a queue data structure. I'll initialize a queue with the root node and an empty result list. While the queue isn't empty, I determine the number of nodes currently in the queue, which represents the width of the current level. I then iterate exactly that many times, dequeuing each node, adding its value to a temporary level list, and enqueuing any non-null children. Once the inner loop finishes, I append the collected level list to my main result array. After the outer loop completes, the result contains levels from top to bottom. To achieve the required bottom-up order, I will simply reverse the entire result list before returning it. This ensures the deepest level appears first. This method maintains an optimal O(N) time complexity since we visit every node once, and O(N) space for the queue and output. At Airbnb, where efficiency matters, this approach guarantees we handle large tree structures without unnecessary computational overhead or complex recursive depth issues.