# LeetCode in Ruby: 102. Binary Tree Level Order Traversal

### Kaitian Xie ・1 min read

LeetCode in Ruby (11 Part Series)

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

LeetCode in Ruby (11 Part Series)

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

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.