I’m experimenting with Binary Trees (Which are very new to me) and am having trouble with one of my functions.
--Testing making binary Trees in Lua
Node = {}
Node.__index = Node
--Constructor
function Node:new(data)
local self = setmetatable({}, Node)
self.leaf = data
self.left = nil
self.right = nil
return self
end
--Methods
function Node:getLeafs()
if not self then
return nil
end
if (self.left == nil and self.right == nil) then
return self.leaf
else
return self.getLeafs(self.left), self.getLeafs(self.right)
end
end
local root = Node:new(1)
root.left = Node:new(2)
root.right = Node:new(3)
root.left.left = Node:new(4)
root.left.right = Node:new(5)
root.right.left = Node:new(6)
root.right.right = Node:new(7)
print(root:getLeafs())
Apart from the fact that some of this may not be correct, as I am also figuring out OOP, it doesn’t function correctly. The method getLeafs() is supposed to return the lowest leafs on the tree, however it skips one of them.
The tree I created in the example:
1
/ \
2 3
/ \ / \
4 5 6 7
The correct output would be:
4 5 6 7
However, the current output is:
4 6 7
I tried removing the 4 leaf, and it comes up as:
nil 6 7
If anyone could help me figure this out, or come up with better code, that would be great! Thanks in advance!
1 Like
Your binary tree is not only nifty, but fine, instead it’s a Lua quirk…
For example take this code block.
function testReturnDepth2()
return 3,4
end
function testReturn()
return testReturnDepth2(), testReturnDepth2()
end
print(testReturn())
The output will be
3 3 4
If we do testReturnDepth2() four times instead of 2, we get
3 3 3 3 4
After some online research, (mainly google), I found this explanation for this quirk.
Lua always adjusts the number of results from a function to the circumstances of the call. When we call a function as a statement, Lua discards all of its results. When we use a call as an expression, Lua keeps only the first result. We get all results only when the call is the last (or the only) expression in a list of expressions. These lists appear in four constructions in Lua: multiple assignment, arguments to function calls, table constructors, and return statements. To illustrate all these uses, we will assume the following definitions for the next examples:
https://www.lua.org/pil/5.1.html
Essentially, if you pass a function as an argument or a return value, and its not alone or the last return value/argument, only the first return value of that function gets returned. So this print will return “3 3 3 4”.
print(testReturnDepth2(),testReturnDepth2(),testReturnDepth2())
You could probably get around this by passing your returns as a table, joining them at the nodes above the leafs.
1 Like
I see, I figured it had something to do with the function returns. The way you suggested I could fix this might work if it was only so deep, however the way i’m planning to go with this requires a bigger and also randomly generated tree. Here’s some different code changes.
function Node:getLeafs()
if self == nil then
return
end
if (self.left == nil and self.right == nil) then
return self
else
return self.getLeafs(self.left), self.getLeafs(self.right)
end
end
local root = Node:new(1)
root.left = Node:new(2)
root.right = Node:new(3)
root.left.left = Node:new(4)
root.left.right = Node:new(5)
root.right.left = Node:new(6)
root.right.right = Node:new(7)
local leafs = {root:getLeafs()}
for i, v in pairs(leafs)do
print(leafs[i].leaf)
end
Output is still 4 6 7
The end result i’m trying to get is all the leafs in an individual table, where I can do whatever I need with them. I’ll have a look at the source you added, and see if there is another way I can achieve this.(I might have to end up using some wierd tricks) But for now, thanks for finding the problem!
You are very close in finding where this rule applies once, yet the rule also applies in another place.
return self.getLeafs(self.left), self.getLeafs(self.right)
There if there is more than one return value of the first function call, than values get dropped.
You could declare a table outside of function scope and insert the leafs into that, but that does not mesh with the Object Oriented Programming style.
A better OOP style would be to return the value of a leaf in a table of {self.leaf}, then on nodes that are not leafs, joining the left table and right table in to a return table. This should result in you getting a table out of it at the end, while keeping with the OOP spirit.
Ah, I think I get what your suggesting here.
At first I thought you meant something else, but I think I see what your actually getting at.
Basically, putting each leaf in its own table:
{4} {5} {6} {7}
then combining the tables into the one:
{4, 5} {6, 7}
{4, 5, 6, 7}
Is this correct? If so how would I go about combining 2 tables, I have yet to do something like that.
Edit: Replied incorrectly
Yep, that’s exactly what I was suggesting. Unfortunately there’s no easy table join method, but looping through the tables and moving the values into a third table is easy enough. Here’s a sample code block.
local table3 = {}
for key,value in pairs(table1) do
table.insert(table3, value)
end
for key,value in pairs(table2) do
table.insert(table3, value)
end
return table3
That works great! Thanks for the help!