CompleteTree.lua

-- Convenience function to explode some text
local function explode(str, separator)
    local out = {}
    
    for w in str:gmatch("([^" .. separator .. "]+)") do out[#out + 1] = w end
    
    return out
end

Node = {}

Node.data = 0
Node.left = nil
Node.right = nil
Node.parent = nil

function Node:new()
	local obj = {}
	setmetatable(obj, self)
	self.__index = self
	
	return obj
end

Tree = {}

Tree.root = nil

-- Some nice ENUMs
Tree.POSTORDER	= 1
Tree.PREORDER	= 2
Tree.LEVELORDER	= 3

function Tree:new()
	local obj = {}
	setmetatable(obj, self)
	self.__index = self
	
	return obj
end

do
	-- Level-order insert
	local function insert(tbl, r, key)
		if (key <= #tbl) then
			local node = Node:new()
			node.data = tbl[key]

			r = node

			r.left = insert(tbl, r, 2 * key)
			r.right = insert(tbl, r, 2 * key + 1)
			
			return r
		end
	end

	function Tree:FromTable(tbl)
		self.root = insert(tbl, self.root, 1)
	end
end

do
	local function bstHelper(node)
		if (not node) then
			return true
		end

		if (node.left and node.left.data > node.data) then
			return false
		end

		if (node.right and node.right.data < node.data) then
			return false
		end

		if (not bstHelper(node.left) or not bstHelper(node.right)) then
			return false
		end

		return true
	end

	function Tree:IsBST()
		return bstHelper(self.root)
	end
end

do
	local function accumulate(mode, t, node, key)
		if (not node) then return end

		if (mode == Tree.PREORDER) then
			t[#t + 1] = node.data

			accumulate(mode, t, node.left)
			accumulate(mode, t, node.right)
		elseif (mode == Tree.POSTORDER) then
			accumulate(mode, t, node.left)
			accumulate(mode, t, node.right)

			t[#t + 1] = node.data
		elseif (mode == Tree.LEVELORDER) then
			if (key == 1) then
				t[#t + 1] = node.data
			elseif (key > 1) then
				accumulate(mode, t, node.left, key - 1)
				accumulate(mode, t, node.right, key - 1)
			end
		end
	end

	function Tree:ToTable()
		local out = {}
		local queue = {self.root}
		
		while (#queue > 0) do
			local levelNodes = #queue
			
			while (levelNodes > 0) do
				local current = queue[1]; table.remove(queue, 1)

				out[#out + 1] = current.data

				if (current.left) then
					queue[#queue + 1] = current.left
				end

				if (current.right) then
					queue[#queue + 1] = current.right
				end
				
				levelNodes = levelNodes - 1
			end
		end

		return out
	end

	function Tree:PreOrder()
		local out = {}
		
		accumulate(self.PREORDER, out, self.root)

		local i = 0
		return function()
			i = i + 1

			return out[i]
		end
	end

	function Tree:PostOrder()
		local out = {}
		
		accumulate(self.POSTORDER, out, self.root)

		local i = 0
		return function()
			i = i + 1

			return out[i]
		end
	end
end

function Tree:BinarySearch(needle)
	local count = 1
	local node = self.root
	
	while (node) do
		if (node.data == needle) then
			return count
		else
			node = needle < node.data and node.left or node.right
			count = count + 1
		end
	end
	
	return count
end

function Tree:LevelSearch(needle)
	local count = 1
	local queue = {self.root}

	while (#queue > 0) do
		local levelNodes = #queue
		
		while (levelNodes > 0) do
			local current = queue[1]; table.remove(queue, 1)
			
			if (current.data == needle) then
				return count
			end

			if (current.left) then
				queue[#queue + 1] = current.left
			end

			if (current.right) then
				queue[#queue + 1] = current.right
			end

			count = count + 1
			
			levelNodes = levelNodes - 1
		end
	end
	
	return count
end

--- Counts how many nodes need to be traversed from root to find the specified value
-- @param value The value to search for
-- @return The number of nodes traversed
function Tree:NumStepsToNode(value)
	if (self:IsBST()) then
		return self:BinarySearch(value)
	else
		return self:LevelSearch(value)
	end
end

-- local tree = Tree:new()

-- local text = nil

-- local commands = {
-- 	toarray				= function(args) for k, v in pairs(tree:ToTable()) do io.stdout:write(v .. " ") end io.stdout:write("\n")	end,
-- 	isbst				= function(args) io.stdout:write(tostring(tree:IsBST()) .. "\n")											end,
-- 	preorder			= function(args) for v in tree:PreOrder() do io.stdout:write(v .. " ") end io.stdout:write("\n")			end,
-- 	postorder			= function(args) for v in tree:PostOrder() do io.stdout:write(v .. " ") end io.stdout:write("\n")			end,
-- 	numnodesinlookup	= function(args) io.stdout:write(tree:NumStepsToNode(tonumber(args[2])))									end
-- }

-- while (text ~= "") do
--     local text = io.stdin:read()

--     if (not text or text == "") then break end
--  
--     local packed = explode(text, " ")
--     local command = string.lower(packed[1])

--     if (not tree.root and #packed > 1) then
-- 		for k, v in pairs(packed) do
-- 			packed[k] = math.floor(tonumber(v)) -- floor everything because decimal math breaks it?
-- 		end

--     	tree:FromTable(packed)
--     end

--     if (commands[command]) then
--     	commands[command](packed)
--     end
-- end