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 from the root downward, you collect levels normally and return them in reverse order.

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

This approach uses classic Breadth-First Search on a binary tree. Push the root into a queue, then process nodes level by level. For each level, iterate through the queue size, collect node values, and enqueue their left and right children. Instead of appending each level directly to the result, push it onto a stack (or prepend to the result). After the traversal finishes, pop levels from the stack to produce the bottom-up order.

The key insight: BFS already groups nodes by depth. Reversing the order of those groups gives the required output without modifying the traversal logic. Each node is visited exactly once, giving O(n) time complexity. The queue and stack together require O(n) space in the worst case.

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

This method performs a depth-first traversal while tracking the current level index. During recursion, create a list for a level when you encounter it for the first time. Append the node value to the list corresponding to its depth. Continue recursively for the left and right children with level + 1. Once the traversal finishes, reverse the list of levels to produce the bottom-up order.

The insight here is that recursion naturally explores the tree structure while maintaining depth information. Instead of grouping nodes during BFS, you group them using their depth index. This approach is concise and easy to implement in languages where recursion is idiomatic. Time complexity remains O(n) since every node is processed once, and the recursion stack plus result storage uses up to O(n) space.

Recommended for interviews: The queue-based BFS solution is what interviewers typically expect. It demonstrates clear understanding of level-order traversal and queue mechanics. The recursive solution is also valid and elegant, but BFS shows stronger familiarity with tree traversal patterns commonly used in production and interview settings.