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.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

basic.rb
Replay: real traced execution (multi-file project)
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(', ')}]"

  1. tree ← 4(2(1,3),6(5,7)), queue ← [4]

    1class Node2  attr_accessor :value, :left, :right
    values this step4(2(1,3),6(5,7))tree[4]queue

  2. output ← [4], queue ← [2, 6]

    16end17queue = [sample_tree]18output = []
    values this step[4]output[2, 6]queue4dequeued

  3. output ← [4, 2], queue ← [6, 1, 3]

    16end17queue = [sample_tree]18output = []
    values this step[4, 2]output[6, 1, 3]queue2dequeued

  4. output ← [4, 2, 6], queue ← [1, 3, 5, 7]

    16end17queue = [sample_tree]18output = []
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

  5. output ← [4, 2, 6, 1], queue ← [3, 5, 7]

    16end17queue = [sample_tree]18output = []
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

  6. output ← [4, 2, 6, 1, 3], queue ← [5, 7]

    16end17queue = [sample_tree]18output = []
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

  7. output ← [4, 2, 6, 1, 3, 5], queue ← [7]

    16end17queue = [sample_tree]18output = []
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

  8. output ← [4, 2, 6, 1, 3, 5, 7], queue ← []

    16end17queue = [sample_tree]18output = []
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. class Node

    1class Node2  attr_accessor :value, :left, :right
    values this step[4, 2, 6, 1, 3, 5, 7]output

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].