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.

binary search tree Values smaller than a node go left; larger values go right.

Visual walkthrough

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

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

  • 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.