# Same fringe toy problem

The “Same Fringe” is a simple and known programming problem:
http://wiki.c2.com/?SameFringeProblem

The problem is:
“two binary trees have the same fringe if they have exactly the same leaves reading from left to right.”

Solving that problem in Python is easy:

``````from itertools import zip_longest

class Leaf:
def __init__(self, v):
self.v = v

class Branch:
def __init__(self, t1, t2):
self.t1, self.t2 = t1, t2

def tree_values(t):
if isinstance(t, Leaf):
yield t.v
elif isinstance(t, Branch):
yield from tree_values(t.t1)
yield from tree_values(t.t2)

def same_fringe(t1, t2):
return all(v1 == v2 for v1, v2 in zip_longest(tree_values(t1), tree_values(t2)))

def main():
L, B = Leaf, Branch

t1 = B(B(L(1), L(2)), L(3))
t2 = B(L(1), B(L(2), L(3)))
print(same_fringe(t1, t2))

t3 = B(L(1), L(2))
print(same_fringe(t1, t3))

main()
``````

I’ve tried to write a similar program in Rust Nightly with similar generators (but I think currently in Rust you can’t do something like the Python `yield from`):

``````#![feature(generator_trait, generators, box_syntax, box_patterns)]

use std::ops::{Generator, GeneratorState};

fn generator_to_iterator<G>(g: G) -> impl Iterator<Item = G::Yield>
where G: Generator<Return = ()> {
struct It<G>(G);

impl<G: Generator<Return = ()>> Iterator for It<G> {
type Item = G::Yield;

fn next(&mut self) -> Option<Self::Item> {
unsafe {
match self.0.resume() {
GeneratorState::Yielded(y) => Some(y),
GeneratorState::Complete(()) => None,
}
}
}
}

It(g)
}

enum Tree { Leaf(u32), Branch(Box<Tree>, Box<Tree>) }

fn tree_values<'a>(t: &'a Tree) -> impl Iterator<Item=u32> + 'a {
generator_to_iterator(move || {
match t {
Tree::Leaf(v) => { yield *v; },
Tree::Branch(ref t1, ref t2) => {
for v in tree_values(t1) { yield v; }
for v in tree_values(t2) { yield v; }
},
}
})
}

fn same_fringe(t1: &Tree, t2: &Tree) -> bool {
tree_values(t1).eq(tree_values(t2))
}

fn main() {
use Tree::{Leaf as L, Branch as B};

let t1 = B(box B(box L(1), box L(2)), box L(3));
let t2 = B(box L(1), box B(box L(2), box L(3)));
let t3 = B(box L(1), box L(2));

println!("{}", same_fringe(&t1, &t2)); // True
println!("{}", same_fringe(&t1, &t3)); // False
}
``````

But it detects a type cycle error. So do I have to box?

Yes, you will need to box, this is because the generator will try to refer to itself (because of the recursive implementation).

This is analogous to

``````struct A {
a: A
}
``````

This means that the generator cannot be constructed. Using a box, you can erase the type (by using trait objects) and implement this.

This is analogous to

``````struct A {
a: Box<A>
}
``````

Actually any pointer indirection with a static lifetime will work (`Arc`, `Rc`, `Vec`, etc.), but in this case `Box` is the best choice.

1 Like

Solved the problem boxing:

``````for v in box tree_values(t1) { yield v; }
for v in box tree_values(t2) { yield v; }``````