Iterative

def level_order(root) result = [] return result if root.nil? queue = [] queue << root until queue.empty? level_size = queue.length level = [] level_size.times do node = queue.shift level << node.val queue << node.left unless node.left.nil? queue << node.right unless node.right.nil? end result << level end result end 

In general, this approach is to go through each level of a given binary tree and add the val of each node to result. For each iteration, we first create an empty level array used to store the values of the nodes at the same level. Then we add the val of each node to the level array and push the nodes at the next level to queue if any. At the end of each iteration, we push the level array to result.

Time complexity: O(n)

Extra memory: O(n)

Recursive

def level_order(root, result = [], level = 0) return result unless root result << [] if result.length == level result[level] << root.val level_order(root.left, result, level + 1) level_order(root.right, result, level + 1) end 

This is similar to the previous approach, except that this one is implemented using recursion. Interestingly, unlike the iterative approach, the recursive approach does not need a queue to temporarily store the nodes at the next level.

Time complexity: O(n)

Extra memory: O(1)