Talk:Same fringe

Pythons binary tree representation

Erm, I looked at the task and immediately thought that building a binary tree in Python might be the part that took the most time and might obfuscate the essence of the task. I did note that some leeway was given in representing the tree.

On looking at the Perl-6 solution I liked the definition of the B-trees a,b,c and x,y,z:

<lang perl-6>my $a = 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8;

my $b = 1 => (( 2 => 3 ) => (4 => (5 => ((6 => 7) => 8)))); my $c = (((1 => 2) => 3) => 4) => 5 => 6 => 7 => 8;

my $x = 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9; my $y = 0 => 2 => 3 => 4 => 5 => 6 => 7 => 8; my $z = 1 => 2 => (4 => 3) => 5 => 6 => 7 => 8;</lang>

I thought this would create valid Python tuples with just a few edit commands in vim and would result in (nested) tuples. Picturing the resultant tuples I then thought of what happens when you traverse a 'true' binary tree, you get the values out in a particular order and that order can be replicated by traversing the Python tuples in a certain way.

So the tuple definitions:

<lang python> a = 1, 2, 3, 4, 5, 6, 7, 8

   b = 1, (( 2, 3 ), (4, (5, ((6, 7), 8))))
   c = (((1, 2), 3), 4), 5, 6, 7, 8

   x = 1, 2, 3, 4, 5, 6, 7, 8, 9
   y = 0, 2, 3, 4, 5, 6, 7, 8
   z = 1, 2, (4, 3), 5, 6, 7, 8</lang>

And the fringe function definition for generating members of the tuples:

<lang python>def fringe(tree):

   'Yield tree members L-to-R depth first, as if stored in a binary tree'
   for node in tree:
       if type(node) != tuple:
           yield node
       else:
           for nd in fringe(node): yield nd</lang>

Act together to emulate the depth first L-to-R traversal of a true binary tree, generating successive leaf values, in order.

The itertools.izip_longest function pairs the successive members of two 'trees' together allowing them to be tested for equality one pair of terms at a time. The all function short circuit evaluates and will return false as soon as the next pair of terms are unequal. The izip_longest function is set to pad a shorter 'tree' with the None value which should not be a member of either tree.
--Paddy3118 15:46, 14 August 2012 (UTC)