On Fri, 9 Aug 2002, Tina Mueller wrote: > > i like the postorder solutions, because there are quite efficient. > the normal approach would be (what i did first, too) to > write a recursive function, because trees somehow belong to > "recursive". function(root) = root . function(child) . function(child2). > but then i realized that the declaration of a sub > just takes away too many space, and i remembered that a) every > algorithm can be done non-recursive and b) perl regexes are > more powerful than one might think. > the regex solution might be a little bit slower than recursive > but it needs less memory. >
I liked the postorder problem because there are so many different approaches. I started with a recursive solution too (79.10): #!/usr/bin/perl $_|=pop;$z|=pop;/[$z]/;$}+=$z=~/$&/;do$0if$z=$`;do$0if$z=$';--$}or$\=$/;print$& But you have to do everything twice for the recursion. And it's a pain to print the \n only at the end -- 16 strokes are dedicated to that! People were already on about 50 by this time, so I knew I had to look for something else. Then I used the following algorithm, which is pretty much what you'd do by hand: Find the first node in the preorder. That's the last node in the postorder. Also change it to a * in the inorder. Now find the last block of letters in the inorder -- that's the rightmost remaining tree. The first of those letters in the preorder is the penultimate node in the postorder. Change it to a * in the inorder as before, and repeat until you've got no more letters left. Here it is in Perl, except with \n used instead of * (63.11): #!/usr/bin/perl -l $_=pop;$ARGV[0]=~/[$&]/,$}=$&.$},s~$&~ ~while/.+ *$/;print$} It was at this point that I realised that it was better to shove the preorder and inorder together in a single string. (Incidentally, when I first read the rules, I thought the lack of specification as to the order of preorder and inorder on the command line was very odd. But it worked very well to avoid prejudicing certain algorithms.) So putting the two orders together in a single string and letting a regexp sort it out got me down to 59.12: #!perl -l $_="@ARGV";$}=$1.$},s~$1~ ~gwhile/(.)\C+\1.* *$/;print$} It's a pretty good improvement from the recursive solution, but I was still 10 off the lead so I looked for a third algorithm. One of the problems with the above solution is that you're compiling the postorder back to front. Could you find the first node in the postorder first, rather than the last node first? Well, yes you can. Here's how, although I found it by staring at letters, and didn't formulate it in this language until later. The first node to be printed in the postorder is the leftmost leaf. The preorder and the inorder also print the leaves from left to right, so we just need to find a criterion for leafness. And the following turns out to be a necessary (but not sufficient) criterion for leafness: the immediately following node in the inorder, if any, must be earlier in the preorder -- the point is that in the inorder, after a leaf you come back up, and in the preorder, ancestors come earlier, descendants later. Now although this isn't a sufficient condition for leafness, it turns out that the leftmost node in the inorder which satisfies this condition IS always a leaf. So you can just find that node, print it out, delete it from the inorder, and repeat. This gave me 54.12: #!perl print s~(.)( |(.).+\3.*\1)~$2~?$1:$/while$2||s//@ARGV/ And finally, we're still going to too much effort to print the \n on the end. There's a neat trick you can play: put the \n at the beginning of the inorder, and it never satisfies the leafness condition until it's the last character left. (If you want to think of it another way, you've defined a new tree which has \n as the top node and the original tree as its right tree, which gives the correct postorder). This leads to my final solution of 49.0913: #!perl s~~ @ARGV~;print$1until!s~(.)( |(.).+\3.*\1)~\2~s Well, I didn't mean to write the whole history of my postorder solution. It just happened! But hopefully it's interesting to someone to see not only what I did but a little bit of how I thought about it. -- Stephen Turner, Cambridge, UK http://homepage.ntlworld.com/adelie/stephen/ "This is Henman's 8th Wimbledon, and he's only lost 7 matches." BBC, 2/Jul/01
