You are here

May 2009

Infix, Prefix, Postfix, Oh My

Any professionally taught programmer eventually has to learn binary trees. Some high school students are exposed early as part of the AP Computer Science AB exam but most have to learn it as part of a data structures course in college.

There are three ways to read a binary tree:

  • Prefix: Root node, then left child, then right child
  • Infix: Left child, then root node, then right child
  • Postfix: Left child, then right child, then root node

Take, for example, this really simple binary tree:

The ways to read this are:

  • Prefix: + 2 3
  • Infix: 2 + 3
  • Postfix: 2 3 +

The infix reading of this tree resembles (and, in fact, is) the standard way we write and interpret simple mathematical equations. "Two plus three equals..." (As an aside, all simple mathematical equations can be expressed as a binary tree. I'm not happy with the tools I have available to render trees right now so I will leave this as an exercise for you, the reader.)

The postfix reading should be familiar to anyone who owns a Hewlett-Packard graphing calculator. This form of representing mathematical equations is most commonly referred to as Reverse Polish notation. Postfix ordering of mathematical expressions is commonly used for rendering stack-based calculators, usually in assignments for a programming class.

The prefix reading resembles the standard way we use constructs in programming languages. If we had to represent "2 + 3" using a function, we would write something like plus( 2, 3 ). This is most clearly shown with LISP's construct ( + 2 3 ). Haskell's backtick operators around infix operators, e.g. `div`, have a side effect of reminding programmers that most functions are prefix-oriented.

So why discuss reading binary trees anyway? In a classroom, teaching the student how to read a binary tree leads to the student being able to program a way to read a binary tree which will then lead to other things. Here, I discuss reading them as background for the next post which may itself lead to other things.

Edit: (11 May 2009) Unfortunately, in the process of writing the next post, I realized that the entire premise of the post was invalid. So the next post will probably not have anything to do with trees.

My PGP key

I finally went through the process of setting up a PGP key. The fingerprint is:

9A86 1FA4 DADE 9C93 F2B0  7C23 38E9 ECDE D61A 0437

You can retrieve the key from a public keyserver or you can download it here.

(There is another PGP key with a fingerprint ending in FCD4 761B but I prefer that it is not used.)

The PGP key was created following the steps used by Ana Guerrero in her blog post.

To make use of PGP, I have set up pinepgp for PINE and Enigmail for Thunderbird. (I'm trying to move away from PINE because it's not working out particularly well but I still have a lot of mail and other such used in it.) I haven't set up PGP on my iBook yet but that's one of my projects for the next few days. I also want to move the PGP keys to a USB drive for security but I haven't started on that process yet either. I will include more information on both when I have them set up.