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)

Using a data structure that requires no recursion seems a bit beyond the spirit of the problem to me. I wouldn't necessarily call it cheating, but it feels like it. Maybe not quite as bad as having a string representation of the tree and then extracting the leaves with a global regex search, but just because you have to pick between down/right/up pointers doesn't really mean you're solving the problem. Kinda like solving a maze by just keeping your right hand on the wall, it requires no brainpower. So I think we should probably eschew the use of parent pointers. Good question though. --TimToady 02:05, 15 August 2012 (UTC)

TimToady picked up on the data structure part of the original question, but I read the question and thought maybe Ledrug was asking about the need of concurrency as in parallel processing? The Python solution does not process each tree in a separate process or thread, which I thought was OK? --Paddy3118 03:51, 15 August 2012 (UTC)

Python yield is basically a coroutine, so the validity is not a problem here. --Ledrug 04:10, 15 August 2012 (UTC)

Coroutines will certainly work, though those can be emulated with closures if you work at it, and the literature also has implementations based on tree rotations, which is mentioned in the description. --TimToady 05:34, 15 August 2012 (UTC)

Tree rotation sounds somewhat iffy. Isn't it essentially the same as massaging (part of) the tree into a singly linked list? --Ledrug 06:12, 15 August 2012 (UTC)