BST Search - Lua DSA

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.

search path A comparison chooses one subtree at each step, so whole branches are skipped.

Visual walkthrough

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

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 search(root, target) local node = root; while node ~= nil do if target == node.value then return true end if target < node.value then node = node.left else node = node.right end end return false end
local root = sample_tree()
print(search(root, 5) and "5 found" or "5 not found")
print(search(root, 8) and "8 found" or "8 not found")

                        

Complexity

Time: O(h) per search
Space: O(1) iterative

Implementation notes

Node(value, left, right) returns a Lua table with value, left, and right fields.
Missing child fields are nil, and sample_tree() builds 4(2(1,3),6(5,7)).
search(root, target) is iterative: it starts with local node = root and loops while node ~= nil.
A match uses if target == node.value then return true end.
Otherwise, target < node.value moves the cursor to node.left; larger targets move to node.right.
If the cursor reaches nil, the function returns false.
The successful target is 5: the trace moves from cursor 4 right, then from 6 left, then matches 5.
The missing target is 8: the trace moves right from 4, right from 6, right from 7, then reaches nil.
The output uses Lua's and/or expression to choose strings, printing 5 found and 8 not found.