Binary trees and binary search trees 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. This is the standard Lua pattern for object-oriented programming. When you write node:insert(5), Lua looks up the insert key in node, finds nothing on the instance table itself, then checks the metatable’s __index reference, which points back to the TreeNode table where all your methods live. Every node shares the same method definitions through this single metatable reference, keeping memory use low even for large trees.

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.

Now let’s see what a tree looks like after several insertions. Starting with a root of 10, the values branch left for smaller numbers and right for larger ones. After inserting 5, 15, 3, 7, 12, and 20, you get a perfectly balanced shape where every non-leaf node has two children and every leaf sits at the same depth. This balanced arrangement is the ideal case: it gives you the fastest possible search, insert, and delete performance.

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

The BST invariant guarantees that every left child is smaller than its parent and every right child is larger. This ordering is what transforms an ordinary tree into a structure you can search in logarithmic time. Without the invariant, you’d have no way to know which direction to go when looking for a value; with it, each comparison cuts the remaining search space in half.

Search: finding values

The BST property is what makes BSTs practical in the first place. In a plain unordered tree, you’d have to scan every node to find a value — an O(n) operation that defeats the purpose of using a tree. But the BST invariant turns each comparison into a decision point, letting you skip entire subtrees at a time.

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. The search function follows the same recursive pattern as insert: compare at the current node, then recurse left or right based on whether the target is smaller or larger than the current value. The recursion bottoms out when you either find a match or hit a nil child, which tells you the value was never inserted.

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

What makes inorder special is that it respects the BST ordering invariant. By visiting the left subtree first (all values smaller than the node), then the node, then the right subtree (all values larger), you naturally get a sorted sequence. This property is why BSTs are often used as ordered sets and sorted maps: the tree stores values in a random-access structure, but inorder traversal reads them back in sorted order without needing a separate sort step.

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

Preorder is the natural choice when you need to reconstruct a tree from its serialized form. By writing the current node’s value first, then the left subtree, then the right subtree, you capture the exact shape of the original tree. When you read the serialized data back, you can rebuild the tree by simply calling insert on each value in preorder: the root always comes first, followed by everything in the left subtree, followed by everything in the right.

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

While preorder captures the tree’s shape for reconstruction, postorder tackles the opposite problem: safe destruction and bottom-up computation. Where preorder answers “what comes first?”, postorder answers “what can I only know after I’ve seen both children?” This makes postorder the go-to traversal for tasks like evaluating arithmetic expression trees and deleting tree structures in languages without garbage collection.

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

Postorder is essential when you need to tear down a tree safely. If you delete a parent node before its children in a language with manual memory management, you lose the references to the children and create a leak. By processing children first, you ensure every node is reachable and can be cleaned up properly. Postorder also comes up in expression tree evaluation, where you must compute the values of subexpressions before you can evaluate their parent operator.

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

The delete function walks down the tree recursively until it finds the target node, then applies the appropriate case. Notice that it returns self at the end of each branch, which lets parent calls reassign their left or right children. This is key to how the deletion propagates back up the call stack, ensuring that every ancestor’s child pointers stay consistent with the new tree shape.

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

root = root:delete(10)

Each of the three deletion cases follows a distinct pattern, and understanding when each applies is key to getting deletion right. The leaf case is trivial: you just sever the parent’s reference to the node and let the garbage collector handle the rest. The one-child case is only slightly harder: you splice the child into the parent’s position, effectively skipping over the deleted node. The two-child case is where things get interesting, requiring the inorder successor swap.

Deleting a leaf node

Deleting a leaf is the simplest case: the node has no children, so nothing needs to be reconnected. The delete function returns nil when it reaches a leaf node matching the target value, and the parent’s recursive call assigns that nil to the appropriate child field. Here it is in action with the value 3, which sits at the bottom of the left subtree with no children of its own:

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

After removing the leaf 3, the parent node 5 simply has its left child set to nil, and the rest of the tree remains untouched. Leaf deletions are the most common case in practice and the cheapest operation: no children to reconnect means the work is done in a single recursive step.

Deleting a node with one child

When a node has only one child, the delete function returns that child instead of nil, splicing it directly into the parent’s position. This bypasses the deleted node while keeping the subtree rooted at the child fully connected to the rest of the tree. Here’s an example where node 3 has acquired a left child 2:

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

The single-line guard if not self.left then return self.right end handles both left-only and right-only children with the same logic. After deletion, the child 2 takes the place of 3 as the left child of 5, and the BST ordering invariant remains intact since all values in the moved subtree are still correctly positioned relative to the new parent.

Deleting a node with two children

Deleting a node with two children is the hardest case. The node has connections to two subtrees that must both be preserved, so you can’t simply return one child. Instead, the algorithm finds the inorder successor: the smallest value in the right subtree. This successor, by definition, has no left child of its own, making it safe to move. Here’s an example deleting 15:

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

After copying the successor’s value and recursively deleting it from the right subtree, the result is a tree where 12 has been promoted to replace 15. Because the successor never has two children, the recursive delete always falls into case 1 or case 2, guaranteeing termination. This pattern of promotion by inorder successor is the standard approach used in virtually every BST implementation.

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