Trees

Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

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.

node links A node stores one value plus references to its left and right children.

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
print(render(sample_tree()))

  1. node ← 1, tree ← 1

    9local function sample_tree()10  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))11end
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    9local function sample_tree()10  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))11end
    values this step3node1, 3tree

  3. node ← 2, tree ← 2(1,3)

    9local function sample_tree()10  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))11end
    values this step2node2(1,3)tree

  4. node ← 5, tree ← 2(1,3), 5

    9local function sample_tree()10  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))11end
    values this step5node2(1,3), 5tree

  5. node ← 7, tree ← 2(1,3), 5, 7

    9local function sample_tree()10  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))11end
    values this step7node2(1,3), 5, 7tree

  6. node ← 6, tree ← 2(1,3), 6(5,7)

    9local function sample_tree()10  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))11end
    values this step6node2(1,3), 6(5,7)tree

  7. node ← 4, tree ← 4(2(1,3),6(5,7))

    9local function sample_tree()10  return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))11end
    values this step4node4(2(1,3),6(5,7))tree

  8. stdout ← 4(2(1,3),6(5,7))

    14end15print(render(sample_tree()))
    values this step4(2(1,3),6(5,7))stdout4(2(1,3),6(5,7))tree

Complexity

  • Time: O(n)
  • Space: O(n)

Implementation notes

  • Node(value, left, right) returns a Lua table with value, left, and right fields.
  • When child arguments are omitted, those fields are nil, making the node a leaf.
  • sample_tree() builds the whole tree with nested calls: Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7))).
  • The trace records leaf construction first: node 1, node 3, then node 2 as 2(1,3).
  • The right side is built as node 5, node 7, then node 6 as 6(5,7).
  • The final root construction is node 4, producing 4(2(1,3),6(5,7)).
  • render(node) returns _ for nil, a bare value for a leaf, and value(left,right) for an internal node.
  • print(render(sample_tree())) prints 4(2(1,3),6(5,7)).