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.

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

Basic Implementation

basic.lua
Replay: real traced execution (multi-file project)
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))

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

    1local function Node(value, left, right)2  return { value = value, left = left, right = right }
    values this step4(2(1,3),6(5,7))tree[4]queue

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

    14end15local queue = {sample_tree()}16local output = {}
    values this step[4]output[2, 6]queue4dequeued

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

    14end15local queue = {sample_tree()}16local output = {}
    values this step[4, 2]output[6, 1, 3]queue2dequeued

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

    14end15local queue = {sample_tree()}16local output = {}
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

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

    14end15local queue = {sample_tree()}16local output = {}
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

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

    14end15local queue = {sample_tree()}16local output = {}
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

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

    14end15local queue = {sample_tree()}16local output = {}
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

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

    14end15local queue = {sample_tree()}16local output = {}
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. print(list_string(output))

    18while 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 end19print(list_string(output))
    values this step[4, 2, 6, 1, 3, 5, 7]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].