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

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
level order Level-order traversal uses a queue to visit shallower nodes first.