LeetCode in Ruby: 102. Binary Tree Level Order Traversal

#leetcode #ruby #binarytree

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)