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 Lua DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.lua 
local function Node(value, left, right)
  return { value = value, left = left, right = right }
end
local function render(node)
  if node == nil then return "_" end
  if node.left == nil and node.right == nil then return tostring(node.value) end
  return tostring(node.value) .. "(" .. render(node.left) .. "," .. render(node.right) .. ")"
end
local function sample_tree()
  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
end
local function list_string(values)
  return "[" .. table.concat(values, ", ") .. "]"
end
local queue = {sample_tree()}
local output = {}
local front = 1
while front <= #queue do local node = queue[front]; front = front + 1; table.insert(output, node.value); if node.left then table.insert(queue, node.left) end; if node.right then table.insert(queue, node.right) end end
print(list_string(output))

Complexity

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

Implementation notes

  • Node(value, left, right) returns a Lua table with value, left, and right fields.
  • sample_tree() builds the checked tree 4(2(1,3),6(5,7)).
  • local queue = {sample_tree()} starts the traversal with the root table in the queue, and local output = {} collects visit order.
  • Instead of table.remove(queue, 1), this source uses local front = 1 and advances front = front + 1 after reading queue[front].
  • The loop condition is while front <= #queue do, so appended children extend the same queue table.
  • Each visit appends with table.insert(output, node.value).
  • Child handling uses truthy table fields: if node.left then ... end and if node.right then ... end; missing children are nil and are skipped.
  • The trace starts with queue [4], then after visiting 4 records output [4] and queue [2, 6].
  • Visiting 2 extends the queue to [6, 1, 3]; visiting 6 extends it to [1, 3, 5, 7].
  • Leaf visits finish output [4, 2, 6, 1, 3, 5, 7], and print(list_string(output)) prints [4, 2, 6, 1, 3, 5, 7].
level order Level-order traversal uses a queue to visit shallower nodes first.