Programs (and expressions) are (usually) written in text form.

To process the text, the text is converted to a tree from, usually with the root at the top.

It can be useful to visualize how an expression is represented in tree form.

Consider the following (fully parenthesized) logical expression.

Draw this expression as a tree diagram (with the root at the top). Do this in three ways (for binary operators).

• infix traversal (operators in the middle)
• prefix traversal (operators after)
• postfix traversal (operators before)

Here is the infix tree and expression for this logical expression.

Note: Unary operators (with only one operand) such as minus "-" are usually written before the operand.

Here is the postfix tree and expression for this logical expression.

Here is the prefix tree and expression for this logical expression.

Note the following about all the trees and expressions.

• The operands appear in the same order regardless of the traversal.
• The tree parts can be moved such that the operators and operands are below their representation in the tree.
• Trees can be represented as nested lists, a future topic.

Here are some questions about expression trees involving arithmetic operators.

Consider an arithmetic expression consisting of 3 (different) arithmetic operators and 4 (different) operands (e.g., integer literals or variables representing integer values). For the examples use here, the following are used.

• 3 (integer) arithmetic operators:
/ : quotient
- : subtraction
+ : addition
• 4 (integer) variable operands:
c
b
m
k

Note: In general, there may be operators and operands that repeat, but for clarity here, the operators and operands used are different.

Note: The operators and operands used here may change from time to time but the concepts remain the same.

Then there are 5 different ways in which to write a well formed arithmetic expression such that in the infix representation of the arithmetic expression the following hold.

• The operators are in the same order left to right.
• The variables are in the same order left to right.
• Only the parentheses are changed.

Note: The ways are given numbers 1 to 5 but those numbers have no relevance other than identifying each way .

The number of ways to parenthesize related to Catalan numbers.

Expressions using parentheses: (math and computer programs)

Expression trees: (computer science processing)

Here is the first few terms in the sequence of Catalan numbers.

They are named after Eugène Catalan (1814-1894), Here are the 5 ways of parenthesizing an expression of 3 binary (arithmetic) operators and 4 (integer) operands.

c / ( b - ( m + k ) )
c / ( ( b - m ) + k )
( c / b ) - ( m + k )
( c / ( b - m ) ) + k
( ( c / b ) - m ) + k

Let us look at an expression tree for each and the ways in which each expression can be written in prefix, infix (as above), and postfix notation.

Starting at the root (top) node, there are three orderings of concern.

• Prefix order: Operator, then left branch, then right branch
• Infix order: Left branch, then operator, then right branch
• Postfix order: Left branch, right branch, operator.

Note: Each branch is either a leaf (operand) or a node that can be considered a sub-tree or tree where that node is the root (of the sub-tree).

Prefix ordering:

( / c ( - b ( + m k ) ) )

Infix ordering:

c / ( b - ( m + k ) )

Postfix ordering:

c b m k + - /

Prefix ordering:

( / c ( + ( - b m ) k ) )

Infix ordering:

c / ( ( b - m ) + k )

Postfix ordering:

c b m - k + /

Prefix ordering:

( - ( / c b ) ( + m k ) )

Infix ordering:

( c / b ) - ( m + k )

Postfix ordering:

c b / m k + -

Prefix ordering:

( + ( / c ( - b m ) ) k )

Infix ordering:

( c / ( b - m ) ) + k

Postfix ordering:

c b m - / k +

Prefix ordering:

( + ( - ( / c b ) m ) k )

Infix ordering:

( ( c / b ) - m ) + k

Postfix ordering:

c b / m - k +

42 questions omitted (login required)