develooper Front page | | Postings from August 2002

Re: Reflections

Thread Previous | Thread Next
Stephen Turner
August 9, 2002 01:23
Re: Reflections
Message ID:
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):


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

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 *

#!/usr/bin/perl -l

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

#!perl -l

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:

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

@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
"This is Henman's 8th Wimbledon, and he's only lost 7 matches." BBC, 2/Jul/01

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About