Trees

BST Insert

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

Algorithm

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))

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

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

Implementation notes

  • Node(value, left, right) returns a Lua table with value, left, and right fields.
  • Missing child fields are nil, which render(node) prints as _.
  • local root = nil starts with an empty tree.
  • The insert order is the Lua table {4, 2, 6, 1, 3, 5, 7}, traversed with ipairs.
  • insert(root, value) returns a new Node(value) when the current subtree is nil.
  • The comparison is value < root.value; smaller values recurse into root.left, while equal-or-larger values recurse into root.right.
  • Child links are updated by assignment: root.left = insert(root.left, value) or root.right = insert(root.right, value).
  • The trace builds 4, then 4(2,_), 4(2,6), 4(2(1,3),6(5,_)), and finally 4(2(1,3),6(5,7)).
  • print(render(root)) outputs 4(2(1,3),6(5,7)).
  • The replay also shows the sorted insert contrast [1, 2, 3, 4], which forms 1(_,2(_,3(_,4))) with height 4 and no rotation.
binary search tree Values smaller than a node go left; larger values go right.