DEV Community

Kaitian Xie
Kaitian Xie

Posted on • Updated on

LeetCode in Ruby: 102. Binary Tree Level Order Traversal

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)

Collapse
 
rnrnshn profile image
Olimpio

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

result << [] if result.length == level
Collapse
 
algobot76 profile image
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.