Construct binary tree of pre-order, post-order and in-order expression

Question

I searched internet and "you tube" but I didn't find any good tutorial for this. How can I draw corresponding "binary tree" of a given expression in “postfix”?

And how would this expression look in infix and prefix?

I don’t know how I should do this step by step :(

18 5 1 + / 4 * 3 5 18 6 / - + -

Note:

The rule for drawing pre-order, post-order and in-order is: 1. pre-order traversal: root, left, right 2. post-order traversal: left, right, root 3. in-order traversal: left root, right

Please I need it for exam

Answer 1

Scan the expression left to right. When you find a number, build a (leaf) node, then push it in a stack. When you find an operator, build a node, pop two nodes from the stack, connect them as left and right son of the current node, then push the node on the stack and continue. At the end of the string, you must have only the root on the stack

When you have the tree, finding prefix and infix is trivial.

Note that this is based on the assumption that every operator takes two values (could be adapted to unary operators easily), that is, every internal node has two children. In general, it is impossible to build a tree from postfix (see wikipedia).