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

### Kaitian Xie twitter logo github logo Feb 28 '19Updated on Dec 16, 2019・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)

DISCUSS (2) Can you explain me the following code? Mainly the <<... #RubyNewbie here

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

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.

Classic DEV Post from Feb 14

## Which Techie Are You?

Join dev.to

Be a better developer. Free forever.  