## DEV Community is a community of 851,150 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Kaitian Xie

Posted on • Updated on

# 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)`

## Discussion (2) Olimpio

Can you explain me the following code? Mainly the <<... #RubyNewbie here

``````result << [] if result.length == level
`````` Kaitian Xie

It means that just before we begin to store the values of the next level, we add an empty array that will be used to store the values.