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)

I think your representation of binary trees is fine, even if it doesn't have explicit CDR pointers. That is, as long as the algorithm has to choose "left" or "right", it's an okay representation. To push it a bit further, a string representation of the whole tree would not be okay if the leaves were extracted directly from the string, but probably would be okay if a stack of cursors were navigating around the string making those left/right/down/up decisions. --TimToady 17:35, 14 August 2012 (UTC)

Thanks. --Paddy3118 22:00, 14 August 2012 (UTC)

Concurrency required?

TimToady obviously had concurrency in mind for this task, but could a solution without it fit the bill? A binary tree can be constructed with each node pointing back to its parent for example, and the tree can be traversed across calls with a single node pointer without thread/coroutine/etc. It sort of violates "no extra work" clause since each node does need some extra information, but it also sort of doesn't because comparison doesn't require extracting the whole tree. What's Larry's stance on this? --Ledrug 01:17, 15 August 2012 (UTC)