Same Fringe

The Same Fringe Problem: Let a binary tree be represented as Tcl list structure. An internal node is a two-element list comprising the left and right subtrees. A leaf node is a one-element list. An empty tree is the empty list.

The problem is to compare whether two trees have the same fringe, that is, have the same leaf nodes when enumerated from left to right. You are allowed to use space only proportional to the depth of the deeper tree, and time only proportional to the size of the tree.

It's fairly easy to write a coroutine to enumerate the fringe of a tree, returning each node in turn:

proc walker {tree} {
    yield [info coroutine]
    worker $tree
    return {}
}

proc worker {tree} {
    if {[llength $tree] == 0} {       # empty subtree
        return
    } elseif {[llength $tree] == 1} { # leaf node
        yield $tree
    } else {                          # internal node
        worker [lindex $tree 0]
        worker [lindex $tree 1]
    }
}

With that sort of enumeration in place, then it's also straightforward to compare the two trees:

proc samefringe {tree1 tree2} {

    # create coroutines to iterate over the leaves
    coroutine w1 walker $tree1
    coroutine w2 walker $tree2

    # compare the trees for equality
    while {[set leaf1 [w1]] eq [set leaf2 [w2]]} {
        if {$leaf1 eq {}} {
            return true
        }
    }

    # trees are not equal. Clean up any unterminated coroutines
    if {$leaf1 ne {}} {rename w1 {}}
    if {$leaf2 ne {}} {rename w2 {}}
    return false
}

And a simple demonstrator program shows that it works:

set tree1 {{a {b {}}} {{c {}} {d {e {}}}}}
set tree2 {{{{{} a} b} {{} c}} {{{} d} e}}
set tree3 {{{{{} a} x} {{} c}} {{{} d} e}}
set tree4 {{{{{} a} b} {{} c}} {{} d}}

puts [samefringe $tree1 $tree2]
puts [samefringe $tree1 $tree3]
puts [samefringe $tree1 $tree4]

Given the constraint that one is not allowed to make a copy of all the leaves, this is a very difficult problem to solve without coroutines, and indeed without Tcl's coroutines that allow yielding from an arbitrary stack depth. (C++ coroutines or Python generators won't help very much: try it!)