Algebraic expressions such as

have an inherent tree-like structure.
For example,
Figure is a representation
of the expression in Equation .
This kind of tree is called
an *expression tree* .

The terminal nodes (leaves) of an expression tree are the variables
or constants in the expression (*a*, *b*, *c*, *d*, and *e*).
The non-terminal nodes of an expression tree are the operators
(+, -, , and ).
Notice that the parentheses which appear in Equation
do not appear in the tree.
Nevertheless, the tree representation has captured the intent of the
parentheses since the subtraction is lower in the tree than the multiplication.

**Figure:** Tree representing the expression *a*/*b*+(*c*-*d*)*e*

The common algebraic operators are either unary or binary. E.g., addition, subtraction, multiplication and division are all binary operations and negation is a unary operation. Therefore, the non-terminal nodes of the corresponding expression trees have either one or two non-empty subtrees. I.e., expression trees are usually binary trees.

What can we do with an expression tree? Perhaps the simplest thing to do is to print the expression represented by the tree. Notice that an inorder traversal of the tree in Figure visits the nodes in the order

Except for the missing parentheses, this is precisely the order in which the symbols appear in Equation !

This suggests that an *inorder* traversal
should be used to print the expression.
Consider an inorder traversal which,
when it encounters a terminal node simply prints it out;
and when it encounters a non-terminal node, does the following:

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

which, despite the redundant parentheses, represents exactly the same expression as Equation .

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.