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)
Top comments (2)
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.