Write a routine that will compare the leaves ("fringe") of two binary trees to determine whether they are the same list of leaves when visited left-to-right. The structure or balance of the trees does not matter; only the number, order, and value of the leaves is important.

Any solution is allowed here, but many computer scientists will consider it inelegant to collect either fringe in its entirety before starting to collect the other one. In fact, this problem is usually proposed in various forums as a way to show off various forms of concurrency (tree-rotation algorithms have also been used to get around the need to collect one tree first). Thinking of it a slightly different way, an elegant solution is one that can perform the minimum amount of work to falsify the equivalence of the fringes when they differ somewhere in the middle, short-circuiting the unnecessary additional traversals and comparisons.

Any representation of a binary tree is allowed, as long as the nodes are orderable, and only downward links are used (for example, you may not use parent or sibling pointers to avoid recursion).

local type, insert, remove = type, table.insert, table.remove
 
None = {} -- a unique object for a truncated branch (i.e. empty subtree)
function isbranch(node) return type(node) == 'table' and #node == 2 end
function left(node) return node[1] end
function right(node) return node[2] end
 
function fringeiter(tree)
    local agenda = {tree}
    local function push(item) insert(agenda, item) end
    local function pop() return remove(agenda) end
    return function()
        while #agenda > 0 do
            node = pop()
            if isbranch(node) then
                push(right(node))
                push(left(node))
            elseif node == None then
                -- continue
            else
                return node
            end
        end
    end
end
 
function same_fringe(atree, btree)
    local anext = fringeiter(atree or None)
    local bnext = fringeiter(btree or None)
    local pos = 0
    repeat
        local aitem, bitem = anext(), bnext()
        pos = pos + 1
        if aitem ~= bitem then
            return false, string.format("at position %d, %s ~= %s", pos, aitem, bitem)
        end
    until not aitem
    return true
end
 
t1 = {1, {2, {3, {4, {5, None}}}}}
t2 = {{1,2}, {{3, 4}, 5}}
t3 = {{{1,2}, 3}, 4}
 
function compare_fringe(label, ta, tb)
    local equal, nonmatch = same_fringe(ta, tb)
    io.write(label .. ": ")
    if equal then
        print("same fringe")
    else
        print(nonmatch)
    end
end
 
compare_fringe("(t1, t2)", t1, t2)
compare_fringe("(t1, t3)", t1, t3)
 