Binary Tree And Prefix & Postfix Notations Of Arithmetic Expressions

We can construct meaningful derivation trees that enable us to represent arithmetic expressions in infix, prefix and postfix forms. A binary tree is enough to represent all these three notations of arithmetic expressions. Both prefix and postfix notations are unintelligable for humans. But they are of great use in computer science. Compilers often convert infix to prefix notation and then to assembler code. From a derivation tree of an algebraic expression, we can get equivalent prefix and postfix notations. An algebraic expression in terms of operators and operands can be derived by an ambiguous context-free grammar. Prefix notation is the parenthesis-free notational scheme invented by Polish logician Jan Lukasiewicz and is often called polish notation. In prefix notation operators are followed by operands.

For example, in prefix notation A + B is written as +AB. Postfix notation is reverse of prefix notation. AB+ is  the equivalent postfix notation of A + B. The infix form is evaluated and the binary tree is created according to the priority of the operators. Let us start from the simplest examples.



Coinsider A+B. Its binary tree representation is:

Now see the binary tree representation for A*B+C.

Binary tree representation of A*B+C

It is easy to understand the method of conversion of infix expression to postfix and prefix notations. When we consider an expression, we divide the expression at the operator with lowest priority. Brackets are used to enhance priority. Operator of highest priority needs to be executed first while executing an expression. But here in this derivation tree method of conversion to infix and prefix notations, we starts from lowest priority operators. Let us start with an example. Let the infix expression be A-B/C+D*E.

The priorities are as follows:

Operators	Priority
Unary +, Unary -, ^	4
*,/,%	3
+,-	2

The chosen example has no brackets in it. We shall see another example with brackets later.

• Check for operator with least priority. In this case we have 2 such operators, plus and minus. Select the right most among them. Here it is +.
• Divide the expression at this operator into two and make + as root node of tree.
• The left side of this operator is the left operand and right side us right operand. Always the left sub-tree of an operator node will be the left operand of the operator and right sub-tree is the right operand of the operator.
• The left half of the expression will be treated similarly and the operator of lowest priority (right most one if more than one occurs) is set as left child (or branch) of root node.
• right half of the expression will also be treated similarly and the operator of lowest priority (right most one if more than one occurs) is set as right child (or branch) of root node.
• The nodes at leaf level will be always operand variables (like A, B etc).

Now, I'll illustrate it with the example.

• Dividing the expression into two halves at operator of lowest priority. Since there are + and -, the right most one among them is selected (+).
• + is selected as root for tree. Now we have to further operate on the two halves on either sides.

•  Now treating the left child of node similarly. - has lowest priority among - and * . Therefore - replaces A-B/C , A becomes left child of - and B/C becomes right child.

• In B/C and D*E, there are only one operator each and they can be converted to corresponding subtrees easily.

This is the binary tree representation of the given infix expression. If you perform an pre-order traversal, you will get the corresponding prefix expression. If you are performing postorder traversal, you'll get postfix expression.


Finally let us consider one more example, an example with parentheses (brackets). Actually, brackets don't make much difference. The only difference is that they make priority differences in execution of operations. An expression gets extra priority if it is enclosed by parentheses. For example, in A+B/C, we have to divide B with C first and then add it to A. But in (A+B)/C, we have to add A with B first and then divide it with C. When making a binary tree for an expression, we treat the expression within brackets as a single variable and proceed. When the expression within brackets become a child of any of the nodes in the tree, we will discard the brackets and treat them as we did with the normal expressions.


Now consider infix expression (A+B)*C/E-D*(F+G) with brackets.

» Here (A+B) and (F+G) are treated as single variables each since they are enclosed in brackets.

» Therefore here minus (-) is the operator of lowest priority. It is selected as root of the binary tree.

» The left side of minus is made the left child and right side is made right child. These two subtrees are next expanded.

» In the left subtree, * and / have same and lowest priority since (A+B) is considered as a single variable. / is selected since it is the right most one. / replaces the node and its right side becomes its right child and left side becomes its left child.

» In the right subtree, * has lowest priority since (F+G) is considered as a single variable. * replaces the node and its right side becomes its right child and left side becomes its left child.

» This process is repeated. The following figures will tell you the rest.