Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

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 function insert(root, value) if root == nil then return Node(value) end if value < root.value then root.left = insert(root.left, value) else root.right = insert(root.right, value) end return root end
local root = nil
for _, value in ipairs({4, 2, 6, 1, 3, 5, 7}) do root = insert(root, value) end
print(render(root))

Complexity

  • Time: O(h) per insert
  • Space: O(n)

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.
binary search tree Values smaller than a node go left; larger values go right.