# Data Structures - Expression Tree

### << Previous Next >>

Expression Tree is used to represent expressions.

An expression and expression tree shown below

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

All the below are also expressions. Expressions may includes constants value as well as variables

`` a * 6 ``
`` 16 ``
``(a^2)+(b^2)+(2 * a * b) ``
`` (a/b) + (c) ``
`` m * (c ^ 2)``

It is quite common to use parenthesis in order to ensure correct evaluation of expression as shown above

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. Examples: a, b, c, 6, 100
• The root and internal nodes are operators. Examples: +, -, *, /, ^
• 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,
• the root, and
• the right expression.

### Postorder Traversal

The postfix expression can be evaluated by recursively printing out

• the left expression,
• the right expression and
• then the root

### Preorder Traversal

We can also evaluate prefix expression by recursively printing out:

• the root,
• the left expressoion and
• the 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:

1. Read one symbol at a time from the postfix expression.
2. Check if the symbol is an operand or operator.
3. If the symbol is an operand, create a one node tree and pushed a pointer onto a stack
4. If the symbol is an operator, pop two pointer from the stack namely T1 & T2 and form a new tree with root as the operator, T1 & T2 as a left and right child
5. 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.

# Data Structures - Expression Tree

### << Previous Next >>

Expression Tree is used to represent expressions.

An expression and expression tree shown below

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

All the below are also expressions. Expressions may includes constants value as well as variables

`` a * 6 ``
`` 16 ``
``(a^2)+(b^2)+(2 * a * b) ``
`` (a/b) + (c) ``
`` m * (c ^ 2)``

It is quite common to use parenthesis in order to ensure correct evaluation of expression as shown above

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. Examples: a, b, c, 6, 100
• The root and internal nodes are operators. Examples: +, -, *, /, ^
• 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,
• the root, and
• the right expression.

### Postorder Traversal

The postfix expression can be evaluated by recursively printing out

• the left expression,
• the right expression and
• then the root

### Preorder Traversal

We can also evaluate prefix expression by recursively printing out:

• the root,
• the left expressoion and
• the 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:

1. Read one symbol at a time from the postfix expression.
2. Check if the symbol is an operand or operator.
3. If the symbol is an operand, create a one node tree and pushed a pointer onto a stack
4. If the symbol is an operator, pop two pointer from the stack namely T1 & T2 and form a new tree with root as the operator, T1 & T2 as a left and right child
5. 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.