Binary Tree Level Order Traversal

  # --- 6. Binary Tree Level Order Traversal ---
  # Problem: Return the level order traversal of a binary tree.
  # Input: [3,9,20,null,null,15,7]
  # Output: [[3],[9,20],[15,7]]
  # Time Complexity: O(n)
  def self.level_order(root)
    return [] if root.nil?
    queue = [ root ]
    result = []

    until queue.empty?
      level = []
      size = queue.size

      size.times do
        node = queue.shift
        level << node.val
        queue << node.left if node.left
        queue << node.right if node.right
      end

      result << level
    end

    result