Binary tree and recursion does my head in [solved]

[togFox]

Binary tree - what super simple obvious thing am I overlooking? When I add node = 5, it works fine. When I then add node = 8, the new node '8' splats the 5 so that only the root is updated and the leafs are not.

Code: Select all

inspect = require 'lib.inspect'

local function insert(tree, node)
    if not next(tree) then
        tree = node
    elseif node.key <= tree.key then
        insert(node.left, node)
    elseif node.key > tree.key then
        insert(node.right, node)
    else
        error()
    end
    return tree
end

function love.load()

	local mytree = {}

    local datapoint = {}
    datapoint.key = 5
    datapoint.left = {}
    datapoint.right = {}
    mytree = insert(mytree, datapoint)

    datapoint.key = 8
    datapoint.left = {}
    datapoint.right = {}
    mytree = insert(mytree, datapoint)
	
	print(inspect(mytree))	-- prints to console
end

[togFox]

Solution provided by zorg

Code: Select all

local function new(key)
    return {key = key, left = nil, right = nil} -- left and right are NOT empty tables, they don't exist at all.
end

local function insert(tree, node)
    if tree == nil then -- if the tree doesn't exist then set inserted node to be the root
        tree = node
    elseif node.key <= tree.key then
        if not tree.left then
            tree.left = node
        else
            insert(tree.left, node)
        end
    elseif node.key > tree.key then
        if not tree.right then
            tree.right = node
        else
            insert(tree.right, node)
        end
    end
    return tree
end

local test = new(5)
insert(test, new(8))
insert(test, new(3))
insert(test, new(4))

print(test.key)
print(test.left.key)
print(test.right.key)
print(test.left.right.key)