DS – Construct Expression Tree from Prefix expression

We have completed 2 conversions using Stack.

1. Infix -> Postfix
2. Infix -> Prefix

We need to use Stack and BST for other 4 conversions

1. Prefix -> Infix (Result doesn’t have parenthesis)
2. Prefix -> Postifx
3. Postfix -> Infix (Result doesn’t have parenthesis)
4. Postfix -> Prefix

Prefix to Postfix:

• Construct Expression tree from Prefix notation
• Post-order traversal results Postfix expression
• In-order traversal results Infix expression

Algorithm to Construct Expression Tree from Prefix expression:

1. Reverse Prefix expression
2. Read element by element
3. If it is operand then
   1. Create leaf node (left and right child are NULL)
   1. Copy the operand into data part
   1. Push Node’s address onto the Stack
4. If it is an operator then
   1. Create a node
   1. Copy the operator into data part
   1. POP address from Stack and assign node->left
   1. POP address from Stack and assign node->right
   1. PUSH node’s address onto the Stack
5. If there is more input, go to step 2
6. If there is no more input, POP the address from stack(which is the root node address)