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