DS – Algorithm to construct Expression tree from Postfix

Algorithm to construct Expression tree from Postfix:

1. Examine the next element in the input
2. If it is operand then
   1. Create the leaf node(right and left child are null)
   1. Copy the operand in data part
   1. Push Node’s address on Stack.
3. If it is an operator then
   1. Create a node
   1. Copy the operator on data part
   1. POP address of node from Stack and assign to node->right
   1. POP address of node from Stack and assign to node->left
   1. PUSH node’s address on Stack.
4. If there is more input, go to step 1
5. If there is no more input, POP the address from Stack which is the address of the root node.