3.6 - Expression Trees

What is an expression tree?

A tree is a data structure that is useful for displaying data that is organized in a hierarchy. The actual data items are stored in locations called nodes and the relationships between the data items are represented by dotted lines called branches. One example is the Folders tree in Windows Explorer. Folders within other folders are displayed further to the right in the tree. Another example is the Table of Contents in the frame just to the left of what you are presently reading. Subtopics within other topics are displayed further to the right (indented) in the tree.

A mathematical expression is also a hierarchy because of the order of mathematical operations, so it can also be displayed in a tree. For example the expression:
a/b*(c+d-e),
which is typeset as:
is represented by the tree shown to the right.

The entire expression, a/b*(c+d-e), is contained in the root node of the tree. It is shown in blue.

This expression contains 3 “factors”, a, b and (c+d-3), that are either multiplied or divided together. Therefore 3 branches come out of this node and each of the factors goes into a node at the end of one of these branches. The red arrow points to these child nodes. (These nodes also contain a * or / symbol to indicate whether this factor is in the numerator or denominator.)

The expression in the third child node, (c+d-e), contains 3 terms, c, d, and e, that are either added or subtracted together. Therefore 3 branches come out of this node and each of the terms goes into a node at the end of one of these branches. The green arrow points to them. (These nodes also contain a + or - symbol to indicate whether this term is added or subtracted.)

This process of breaking the expression into ever smaller parts, with the tree growing from left to right, continues until every branch ends with a node containing either a number or a variable that represents a number.


When an expression is evaluated, the evaluations travel back through the nodes from right to left. Every child node must have a value before its parent node can be evaluated. Here is an example showing how the expression a b + c d is evaluated with a = 2, b = 3, c = 4, d = 5. Follow the sequence of pictures and notice how the numbers shown in red appear.




Functions are represented as shown in this example:
5 sin (3 x + 2).
The node containing the function (shown in blue) is the root of a brand new tree that holds the argument of the function. Before the function can be evaluated this tree must be evaluated.


Exponentials are represented as shown in this example of the expression:
The node containing the exponential (shown in blue) is the root of two new trees, one that holds the exponent (indicated by the caret symbol, ^, and pointed to by the red arrow) and one that holds the base. Before the exponential can be evaluated both of these trees must be evaluated.



What can an expression tree show you?

An expression tree is useful for: