# Data Structures - Expression Tree

Expression Tree is used to represent expressions. There are different types of expression formats:

- Prefix expression
- Infix expression and
- Postfix expression

Expression Tree is a special kind of binary tree with the following properties:

- Each leaf is an operand.
- The root and internal nodes are operators.
- Subtrees are subexpressions with the root being an operator.

### Traversal Techniques

There are 3 standard traversal techniques to represent the 3 different expression formats.

#### Inorder Traversal

We can produce an infix expression by

- recursively printing out the left expression,
- then printing out the root, and
- recursively printing out right expression.

#### Postorder Traversal

The postfix expression can be evaluated by

- recursively printing out the left expression,
- right expression and
- then root

#### Preorder Traversal

We can also evaluate prefix expression by:

- printing out the root and
- then recursively print out the left and
- right expression.

If we apply all these strategies to the sample tree above, the outputs are:

- Infix expression:
`(a+(b*c))+(d*(e + f))`

- Postfix Expression:
`a b c * + d e f + * +`

- Prefix Expression:
`+ + a * b c * d + e f`

### Construction of Expression Tree

We consider that a postfix expression is given as an input for constructing an expression tree. Following are the step to construct an expression tree:

- Read one symbol at a time from the postfix expression.
- Check if the symbol is an operand or operator.
- If the symbol is an operand, create a one node tree and pushed a pointer onto a stack
- If the symbol is an operator, pop two pointer from the stack namely T
_{1}& T_{2}and form a new tree with root as the operator, T_{1}& T_{2}as a left and right child - A pointer to this new tree is pushed onto the stack

### Example

The input is:

` a b + c * `

The first two symbols are operands, we create one-node tree and push a pointer to them onto the stack.

Next, read a**'+'** symbol, so two pointers to tree are popped,a new tree is formed and push a pointer to it onto the stack.

Next, **'c'** is read, we create one node tree and push a pointer to it onto the stack.

Finally, the last symbol is read ** ' * '**, we pop two tree pointers and form a new tree with a, **' * '** as root, and a pointer to the final tree remains on the stack.