Trees

BST Search

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

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.

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

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
search path A comparison chooses one subtree at each step, so whole branches are skipped.