BinarySearchTree

local BinarySearchTree = {}
BinarySearchTree.__index = BinarySearchTree

local push = table.insert
local pop = table.remove

-- Inserts a unique value into the binary search tree.
-- Returns true if the value was valid and inserted.
function BinarySearchTree:Insert(value)
    if value == nil then
        return false
    end

    local node = self.Root

    while node.Value do
        if value < node.Value then
            node = node.Left
        elseif value > node.Value then
            node = node.Right
        else
            return false
        end
    end

    node.Value = value
    node.Right = {}
    node.Left = {}

    return true
end

-- Returns an iterator function that performs an
-- in-order traversal of the binary search tree.
function BinarySearchTree:Iterate()
    return coroutine.wrap(function ()
        local stack = {}
        local visited = {}

        local node = self.Root
        local index = 1

        while node do
            -- Visit the left node
            local left = node.Left

            if left and not visited[left] then
                push(stack, node)
                node = left
            else
                -- Visit this node
                if not visited[node] then
                    local value = node.Value

                    if value then
                        coroutine.yield(index, value)
                        index = index + 1
                    end

                    visited[node] = true
                end

                -- Visit the right node
                local right = node.Right

                if right and not visited[right] then
                    push(stack, node)
                    node = right
                else
                    node = pop(stack)
                end
            end
        end
    end)
end

-- Constructs a new BinarySearchTree.
function BinarySearchTree.new()
    local tree = {}
    tree.Root = {}

    return setmetatable(tree, BinarySearchTree)
end

return BinarySearchTree