Expression Tree

Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand. Consider the expression:

(a + b*c) * ( d + e)

It can be represented as a binary tree as

In-order traversal, reconstructs the expression:  (a + b*c) * ( d + e) i.e Infix notation. Post-order traversal results in the corresponding postfix expression: a b c * + d e + *.

Given a postfix expression, we can construct the expression tree, using a stack that contains pointers to the tree nodes. We loop through input expression and do following for every character.

• If the symbol is an operand, we create a one-node tree and push a pointer to it into a stack.
• If the symbol is an operator, we pop twice pointers to two trees T1 and T2 (T1 is popped first) and form a new tree whose root is the operator and whose left and right children are T2 and T1, respectively. A pointer to this new tree is then pushed onto the stack.

Example: Consider the expression (a + b) * (c * (d + e)). The postfix expression is:

a b + c d e + * *

Steps for constructing expression tree

1. The first tow symbols are operands, so we create one-node trees and push pointers to them onto a stack.
2. Next, we read ‘+’ so two pointers to trees are popped, a new tree is formed, and a pointer to it is pushed onto the stack.
3. Next, c, d, and e are read, and for each a one-node tree is created and a pointer to the corresponding tree is pushed onto the stack.
4. Then we read ‘ + ‘ and two trees are having ‘d’ and ‘e’ as root are merged.
5. Then, ‘ * ‘ is read, so we pop two tree pointers  (root nodes are ‘c’ and ‘+’ ) and form a new tree with ‘*’ as  root.
6. Finally, the last symbol ‘*’ is read, two trees are merged, and a pointer to the final tree is pushed onto the stack.

As all the operators in the tree are binary hence each node will have either 0 or 2 children. As it can be inferred from the examples above , the integer values would appear at the leaf nodes , while the interior nodes represent the operators. To evaluate a recursive approach can be followed.

// Let t be the syntax tree
If  t is not null then
      If t.val is operand then  
         return  t.val
      else
         A = solve(t.left)
         B = solve(t.right)
         return A t.operator B

Reference :-

Expression Tree