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).

--
-- demo\rosetta\Same_Fringe.exw
-- ============================
--
--  In some cases it may help to replace the single res with a table, such
--  that if you have concurrent task pairs {1,2} and {3,4} with a table of
--  result indexes ridx = {1,1,2,2}, then each updates res[ridx[tidx]]. In
--  other words if extending tasks[] rather than overwriting it, you would
--  also extend res[] and ridx[] and sdata[], and need freelist handling.
--
without js -- (multitasking)

constant tests = {{0,1,{0,2,0}},
                  {{0,1,0},2,0},
                  {{0,1,0},2,{0,3,0}},
                 }

sequence tasks,
         sdata = repeat(0,2)
integer res = 0,
        active_tasks
bool show_details = true

procedure scan(sequence tree, integer level, integer tidx)
    object {left,data,right} = tree
    if res=0 then
        if left!=0 then scan(left,level+1,tidx) end if
        sdata[tidx] = data
        if show_details then
            printf(1,"task[%d] sets sdata[%d] to %v\n",{tidx,tidx,data})
        end if
        if res=0 then
            task_suspend(task_self())
            task_yield()
        end if
        if right!=0 then scan(right,level+1,tidx) end if
    end if
    if level=1 then
        if show_details then
            printf(1,"task[%d] ends\n",tidx)
        end if
        active_tasks -= 1
        tasks[tidx] = 0
        sdata[tidx] = -1 -- (or use a separate flag or tasks[tidx])
    end if
end procedure

procedure test(integer t1, t2)
    tasks = {task_create(routine_id("scan"),{tests[t1],1,1}),
             task_create(routine_id("scan"),{tests[t2],1,2})}
    active_tasks = 2
    res = 0
    while active_tasks>0 do
        for i=1 to 2 do
            if tasks[i] then
                task_schedule(tasks[i],1)
                task_yield()
            end if
        end for
        if res=0 then
            -- (nb next might only be valid for active_tasks==2)
            res = compare(sdata[1],sdata[2])
            if show_details then
                printf(1,"compare(%v,%v) ==> %d, active tasks:%d\n",
                         {sdata[1],sdata[2],res,active_tasks})
            end if
        end if
    end while
    printf(1,"test(%d,%d):%d\n",{t1,t2,res})
end procedure

?"started"
for l=1 to 3 do
    for r=1 to 3 do
        test(l,r)
        show_details = 0
    end for
end for

?"done"
{} = wait_key()
