Prefix Notation

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Prefix Notation

In prefix notation the operator is written before its operands. Therefore, in order to print the prefix expression from an expression tree, preorder traversal is done. I.e., at every non-terminal node we do the following:

Print the root; and then
print a left parenthesis; and then
traverse the left subtree; and then
print a comma; and then
traverse the right subtree; and then
print a right parenthesis.

If we use this procedure to print the tree given in Figure

we get the prefix expression

While this notation may appear unfamiliar at first, consider the result obtained when we spell out the names of the operators:

plus (div (a,b), times (minus (c,d), e))

This is precisely the notation used in a typical programming language to invoke user defined procedures plus, minus, times, and div.