Binary Tree Level Order Traversal II - Video Solutions

Problem Overview: Given the root of a binary tree, return the level order traversal of its nodes from bottom to top. Instead of listing levels starting from the root, you collect nodes level by level and return them in reverse order so the deepest level appears first.

Approach 1: Level Order Traversal with Queue and Stack (O(n) time, O(n) space)

This approach performs a standard BFS using a queue. Start by pushing the root into the queue, then repeatedly process nodes level by level. For each level, iterate through the current queue size, pop nodes, record their values, and push their children. Instead of appending each level directly to the result, push the level list onto a stack. After BFS finishes, pop from the stack to build the final bottom‑up order. Every node is visited exactly once, giving O(n) time complexity and O(n) auxiliary space for the queue, stack, and result. This is the most intuitive solution because it mirrors the normal Breadth-First Search traversal while simply reversing the level order.

Approach 2: Recursive Level Order Traversal (O(n) time, O(n) space)

This solution uses DFS recursion while tracking the current depth. Maintain a list of lists where each index corresponds to a tree level. During recursion, if the current depth equals the size of the result list, create a new level container. Insert the node value into the corresponding level, then recursively process the left and right children with depth + 1. Once traversal finishes, reverse the collected levels to produce the bottom‑up ordering. Each node is processed once, so the time complexity remains O(n), while recursion depth and storage require O(n) space in the worst case for a skewed tree. This approach works well if you prefer recursive logic over queue-based iteration.

Recommended for interviews: The BFS queue approach is typically expected because it directly matches the definition of level order traversal in a binary tree. Using a stack (or reversing the result) to adjust the order shows you understand traversal mechanics. Recursive level construction demonstrates deeper control over tree traversal but is slightly less direct for this problem.