What is an expression tree? How an expression is evaluated using an expression tree? Discuss its advantages over the other evaluation techniques.

Algebraic expressions such as 

a/b+(c-d)e  

have an inherent tree-like structure. For example, following figure is a representation of the expression in above equation. This kind of tree is called an expression tree. 

 

Fig: Example of 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 theoperators (+, -, x, / and )
 

The expression tree is evaluated using a post-order traversal of the expression tree as follows:

0. 1. If this node has no children, it should return the value of the node
      
   2. Evaluate the left hand child
      
   3. Evaluate the right hand child
      
   4. Then evaluate the operation indicated by the node and return this value
      
   
   

   Advantages of expression tree

   
   
   • Understanding the order of operation. Operations that must be done sooner are further to the right in the tree.
   • Counting the number of terms or factors in an expression. Each term or factor is a child node. For example the expression (a+b)/c+2*d contains two terms.