Trees

BST Search

Search a binary search tree for one present and one absent value.

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

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.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

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

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot 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.
search path A comparison chooses one subtree at each step, so whole branches are skipped.