Expression Trees

The expression tree is a binary tree in which each internal node corresponds to the operator and each leaf node corresponds to the operand so for example expression tree for 3 + ((5+9)*2) would be:

Inorder traversal of expression tree produces infix version of given postfix expression (same with postorder traversal it gives postfix expression)

Evaluating the expression represented by an expression tree: 

Let t be the expression tree
If  t is not null then
      If t.value is operand then  
                Return  t.value
      A = solve(t.left)
      B = solve(t.right)
 
      // calculate applies operator 't.value' 
      // on A and B, and returns value
      Return calculate(A, B, t.value)Code language: PHP (php)

Construction of Expression Tree: 

Now for constructing an expression tree we use a stack. We loop through input expression and do the following for every character. 

1. If a character is an operand push that into the stack
2. If a character is an operator pop two values from the stack make them its child and push the current node again.

In the end, the only element of the stack will be the root of an expression tree.