Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Ruby DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.rb 
class Node
  attr_accessor :value, :left, :right
  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
end
def render(node)
  return "_" if node.nil?
  return node.value.to_s if node.left.nil? && node.right.nil?
  "#{node.value}(#{render(node.left)},#{render(node.right)})"
end
def sample_tree
  Node.new(4, Node.new(2, Node.new(1), Node.new(3)), Node.new(6, Node.new(5), Node.new(7)))
end
queue = [sample_tree]
output = []
until queue.empty?
  node = queue.shift
  output << node.value
  queue << node.left if node.left
  queue << node.right if node.right
end
puts "[#{output.join(', ')}]"

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • Node is the same Ruby class shape as the tree-build lesson, with attr_accessor :value, :left, :right and nil for missing children.
  • queue = [sample_tree] stores node objects in a Ruby array used as a queue.
  • The loop runs until queue.empty?, so queue.shift is only called when a front node exists.
  • node = queue.shift removes the oldest queued node, and output << node.value records its value.
  • Children are enqueued with queue << node.left if node.left and then queue << node.right if node.right, so nil children are skipped.
  • Left-before-right enqueue order is visible in the trace: after 4, the queue is [2, 6]; after 2, it is [6, 1, 3].
  • The replay drains the queue in level order: 4, 2, 6, 1, 3, 5, 7.
  • puts "[#{output.join(', ')}]" prints the final bracketed list [4, 2, 6, 1, 3, 5, 7].
level order Level-order traversal uses a queue to visit shallower nodes first.