Binary Trees and BSTs in Lua

Binary trees are one of the most important data structures in computer science. They appear everywhere—from database indexes to file systems to expression parsers. In this tutorial, you’ll learn what binary trees are, how the Binary Search Tree (BST) ordering works, and how to implement the core operations in clean, idiomatic Lua.

What is a Binary Tree?

A binary tree is a hierarchical structure where each node holds a value and can have at most two children: a left child and a right child. The topmost node is called the root. Nodes with no children are called leaves. Everything else sits somewhere in between—a single parent with up to two children.

       10
      /  \
     5    15
    / \   / \
   3   7 12  20

In this example, 10 is the root, 3, 7, 12, and 20 are leaves, and 5 and 15 are internal nodes with one parent and up to two children each.

Binary trees matter because they let you store and retrieve data efficiently. Where an array forces you to scan linearly or a linked list chains data sequentially, a well-balanced binary tree cuts your search space in half at every step. That turns what would be O(n) operations into O(log n) ones—exactly the kind of scaling that separates toy programs from production systems.

Binary Search Tree — The Invariant

A plain binary tree has no ordering, which limits its usefulness. The Binary Search Tree (BST) adds a single rule that changes everything:

For any node N, every value in the left subtree of N is less than N’s value, and every value in the right subtree of N is greater than N’s value.

This is called the BST invariant, and it is what makes searching fast. To find a value, you compare it to the current node and go left if it’s smaller, right if it’s larger. At each step, you eliminate half the remaining tree. In a balanced BST with a million nodes, you need at most 20 comparisons to find any value.

The tradeoff is that the invariant only holds if you maintain it during insertion. Every new value must be placed in the correct spot to preserve the ordering.

Node Representation in Lua

Lua tables are perfect for representing tree nodes. They’re flexible, dynamically typed, and support keyed access. Here’s how you define a node class using a metatable:

local TreeNode = {}
TreeNode.__index = TreeNode

function TreeNode:new(value)
    local node = setmetatable({}, TreeNode)
    node.value = value
    node.left = nil
    node.right = nil
    return node
end

Each node table has three fields:

• value — the stored data
• left — reference to the left child subtree (or nil)
• right — reference to the right child subtree (or nil)

The metatable with __index = TreeNode lets you call methods on node instances using the familiar node:method(args) syntax.

Insert — Building the Tree

Insertion places a new value in the correct position while maintaining the BST invariant. The recursive approach mirrors how you’d search: compare the value to the current node and recurse left or right until you find an empty spot.

function TreeNode:insert(value)
    if value < self.value then
        if self.left then
            self.left:insert(value)
        else
            self.left = TreeNode:new(value)
        end
    elseif value > self.value then
        if self.right then
            self.right:insert(value)
        else
            self.right = TreeNode:new(value)
        end
    end
    -- Duplicate values are ignored
end

Notice that equal values are simply dropped. You could handle duplicates differently—for example, by storing a count—but for this implementation, each value appears at most once.

Here’s a complete example building a tree:

local root = TreeNode:new(10)
root:insert(5)
root:insert(15)
root:insert(3)
root:insert(7)
root:insert(12)
root:insert(20)

-- Tree structure:
--        10
--       /  \
--      5    15
--     / \   / \
--    3   7 12  20

Search — Finding Values

The BST invariant makes search straightforward. Compare the target to the current node and recurse into the appropriate child. If you reach a nil child, the value isn’t in the tree.

function TreeNode:search(value)
    if value == self.value then
        return self
    elseif value < self.value and self.left then
        return self.left:search(value)
    elseif value > self.value and self.right then
        return self.right:search(value)
    end
    return nil
end

This returns the node itself if found, or nil if the value doesn’t exist. Here’s how to use it:

local found = root:search(7)
print(found and found.value or "nil") --> 7

local missing = root:search(99)
print(missing and missing.value or "nil") --> nil

Traversal — Inorder, Preorder, and Postorder

Traversal algorithms visit every node in the tree. Each order produces different results and serves different purposes.

Inorder Traversal (Left, Root, Right)

Inorder traversal visits the left subtree, then the node itself, then the right subtree. For a BST, this produces values in sorted ascending order—the single most useful property of binary search trees.

function TreeNode:inOrder(result)
    result = result or {}
    if self.left then
        self.left:inOrder(result)
    end
    table.insert(result, self.value)
    if self.right then
        self.right:inOrder(result)
    end
    return result
end

local sorted = root:inOrder()
print(table.concat(sorted, ", ")) --> 3, 5, 7, 10, 12, 15, 20

That output—values in perfect sorted order with no extra sorting step—is the signature feature of a BST.

Preorder Traversal (Root, Left, Right)

Preorder visits the node before its children. This is useful when copying or serializing a tree, because you record each node before descending into its subtrees.

function TreeNode:preOrder(result)
    result = result or {}
    table.insert(result, self.value)
    if self.left then
        self.left:preOrder(result)
    end
    if self.right then
        self.right:preOrder(result)
    end
    return result
end

local pre = root:preOrder()
print(table.concat(pre, " -> ")) --> 10 -> 5 -> 3 -> 7 -> 15 -> 12 -> 20

Postorder Traversal (Left, Right, Root)

Postorder visits both children before the node itself. This is the natural order for deleting a tree, because you clean up children before removing their parent.

function TreeNode:postOrder(result)
    result = result or {}
    if self.left then
        self.left:postOrder(result)
    end
    if self.right then
        self.right:postOrder(result)
    end
    table.insert(result, self.value)
    return result
end

local post = root:postOrder()
print(table.concat(post, " -> ")) --> 3 -> 7 -> 5 -> 12 -> 20 -> 15 -> 10

Delete — The Three Cases

Deletion is the most complex BST operation. The difficulty depends on how many children the target node has.

Case 1: Leaf node (no children). Simply remove it—there are no connections to maintain.

Case 2: One child. Bypass the deleted node by connecting its parent directly to its child.

Case 3: Two children. This is the tricky case. Find the inorder successor (the smallest value in the right subtree). Copy that value into the node you’re deleting, then recursively delete the successor from the right subtree.

function TreeNode:delete(value)
    if value < self.value then
        self.left = self.left and self.left:delete(value)
    elseif value > self.value then
        self.right = self.right and self.right:delete(value)
    else
        -- Found the node to delete
        if not self.left then return self.right end
        if not self.right then return self.left end

        -- Two children: find inorder successor
        local successor = self.right
        while successor.left do
            successor = successor.left
        end
        self.value = successor.value
        self.right = self.right:delete(successor.value)
    end
    return self
end

Critical: Always reassign the result when deleting from the root:

root = root:delete(10)

Deleting a Leaf Node

root = root:delete(3)
local sorted = root:inOrder()
print(table.concat(sorted, ", ")) --> 5, 7, 10, 12, 15, 20

Deleting a Node with One Child

root:insert(2)
-- Before: 3 has left child 2
root = root:delete(3)
-- After: 2 becomes left child of 5
local sorted = root:inOrder()
print(table.concat(sorted, ", ")) --> 2, 5, 7, 10, 12, 15, 20

Deleting a Node with Two Children

-- Delete 15 (has two children: 12 and 20)
root = root:delete(15)
local sorted = root:inOrder()
print(table.concat(sorted, ", ")) --> 2, 5, 7, 10, 12, 20

Performance and Balance

The power of a BST comes from balance. When the tree is balanced, the height is roughly log₂(n), and search, insert, and delete all run in O(log n) time. When the tree is unbalanced—because data arrived in a poor order—the height approaches n, and performance degrades to O(n), no better than a linked list.

Tree State	Time Complexity	Height
Balanced	O(log n)	log₂(n)
Degenerate	O(n)	n

Inserting sorted data into a naive BST produces a tree shaped like a linked list:

local degenerate = TreeNode:new(1)
degenerate:insert(2)
degenerate:insert(3)
degenerate:insert(4)
degenerate:insert(5)
-- Now it's basically 1 -> 2 -> 3 -> 4 -> 5

To prevent this, self-balancing variants exist:

• AVL trees — maintain a strict height difference of at most 1 between subtrees
• Red-Black trees — use color rules to approximate balance
• Treaps — use randomization for probabilistic balance

For most Lua projects, a plain BST is fine for moderate datasets. Just be aware that sorted input is its Achilles heel.

A Complete Example

Here’s everything together—a self-contained script you can run:

local TreeNode = {}
TreeNode.__index = TreeNode

function TreeNode:new(value)
    local node = setmetatable({}, TreeNode)
    node.value = value
    node.left = nil
    node.right = nil
    return node
end

function TreeNode:insert(value)
    if value < self.value then
        if self.left then
            self.left:insert(value)
        else
            self.left = TreeNode:new(value)
        end
    elseif value > self.value then
        if self.right then
            self.right:insert(value)
        else
            self.right = TreeNode:new(value)
        end
    end
end

function TreeNode:search(value)
    if value == self.value then
        return self
    elseif value < self.value and self.left then
        return self.left:search(value)
    elseif value > self.value and self.right then
        return self.right:search(value)
    end
    return nil
end

function TreeNode:inOrder(result)
    result = result or {}
    if self.left then
        self.left:inOrder(result)
    end
    table.insert(result, self.value)
    if self.right then
        self.right:inOrder(result)
    end
    return result
end

function TreeNode:delete(value)
    if value < self.value then
        self.left = self.left and self.left:delete(value)
    elseif value > self.value then
        self.right = self.right and self.right:delete(value)
    else
        if not self.left then return self.right end
        if not self.right then return self.left end
        local successor = self.right
        while successor.left do
            successor = successor.left
        end
        self.value = successor.value
        self.right = self.right:delete(successor.value)
    end
    return self
end

-- Build a tree
local root = TreeNode:new(10)
root:insert(5)
root:insert(15)
root:insert(3)
root:insert(7)
root:insert(12)
root:insert(20)

-- Test search
print(root:search(7).value) --> 7
print(root:search(99) or "nil") --> nil

-- Inorder traversal gives sorted output
local sorted = root:inOrder()
print(table.concat(sorted, ", ")) --> 3, 5, 7, 10, 12, 15, 20

-- Delete and verify
root = root:delete(15)
print(table.concat(root:inOrder(), ", ")) --> 3, 5, 7, 10, 12, 20

Summary

Binary Search Trees are a foundational data structure that combines hierarchical organization with efficient searching. The BST invariant—all left subtree values are smaller, all right subtree values are larger—enables O(log n) operations that would be O(n) in linear structures.

In Lua, nodes are naturally represented as tables with left and right child references. The key operations—insert, search, and delete—all follow the same recursive pattern: compare, recurse, and handle the base case.

The main caveat is balance. A BST built from randomly ordered data stays fast. A BST built from sorted data collapses into a line. For production systems that need guaranteed performance, consider AVL trees or Red-Black trees. For everyday Lua scripts and moderate datasets, a plain BST is more than sufficient.

See Also

• Linked Lists in Lua — another fundamental data structure for sequential data
• Hash Maps in Lua — fast key-value lookup using hash tables