Question

Draw the ordered rooted tree corresponding to each of these arithmetic expressions written in prefix notation. Then write each expression using infix notation.

1. \({\bf{ + }} * {\bf{ + - 53214}}\)
2. \( \uparrow {\bf{ + }}23{\bf{ - }}51\)
3. \( * {\bf{/93 + }} * {\bf{24 - 76}}\)

Short answer

a) Therefore, the infix notation of the expression is \(\left( {\left( {\left( {\left( {5 - 3} \right) + 2} \right) * 1} \right) + 4} \right)\) and its ordered rooted tree is shown below.

b) Hence, the infix notation of the expression is \(\left( {\left( {{\bf{2 + 3}}} \right) \uparrow \left( {{\bf{5 - 1}}} \right)} \right)\) and its ordered rooted tree is shown below.

c) So, the infix notation of the expression is \(\left( {\left( {9/3} \right) * \left( {\left( {2 * 4} \right){\bf{ + }}\left( {7{\bf{ - }}6} \right)} \right)} \right)\) and its ordered rooted tree is shown below.

Step-by-step solution

General form

Preorder traversal:

Let T be an ordered rooted tree with root r. If T consists only of r, then r is the preorder traversal of T. Otherwise, suppose that\({T_1},{T_2},...,{T_n}\)are the subtrees at r from left to right in T. The preorder traversal begins by visiting r. It continues by traversing\({T_1},\)in preorder, then\({T_2}\)in preorder, and so on, until\({T_n}\)is traversed in preorder.

Postorder traversal:

Let T be an ordered rooted tree with root r. If T consists only of r, then r is the postorder traversal of T. Otherwise, suppose that\({T_1},{T_2},...,{T_n}\)are the subtrees at r from left to right. The postorder traversal begins by traversing\({T_1},\)in postorder, then\({T_2}\)in postorder, …, then\({T_n}\)in postorder, and ends by visiting r.

Inorder traversal:

Let T be an ordered rooted tree with root r. If Tconsists only of r, then r is the inorder traversal of T. Otherwise, suppose that\({T_1},{T_2},...,{T_n}\)are the subtrees at r from left to right. The inorder traversal begins by traversing\({T_1},\)in inorder, then visiting r. It continues by traversing\({T_2}\)in inorder, and so on, until\({T_n}\)is traversed in inorder.

Note: Since the prefix, postfix and infix form of this expression are founded by traversing this rooted tree in preorder, post order and inorder (including parentheses), respectively.

(a) Represent the given expression using binary tree

Given that, the prefix notation is \({\bf{ + }} * {\bf{ + }} - {\bf{53214}}\).

Let us draw the ordered rooted tree for the given prefix notation

So, the expression is \(\left( {\left( {\left( {5 - 3} \right) + 2} \right) * 1} \right) + 4\).

Now convert the expression in the infix form.

Since, the infix form of the expression is fully covered. So, \(\left( {\left( {\left( {\left( {5 - 3} \right) + 2} \right) * 1} \right) + 4} \right)\)is the infix form of expression.

(b) Represent the given expression using binary tree

Given that, the prefix notation is \( \uparrow {\bf{ + }}23 - 51\).

Let us draw the ordered rooted tree for the given prefix notation.

So, the expression is \(\left( {{\bf{2 + 3}}} \right) \uparrow \left( {{\bf{5 - 1}}} \right)\).

Now convert the expression in the infix form.

Since, the infix form of the expression is fully covered. So, \(\left( {\left( {{\bf{2 + 3}}} \right) \uparrow \left( {{\bf{5 - 1}}} \right)} \right)\) is the infix form of expression.

(c) Represent the given expression using binary tree

Given that, the prefix notation is \( * {\bf{/93 + }} * {\bf{24 - 76}}\).

Let us draw the ordered rooted tree for the given prefix notation.

So, the expression is \(\left( {9/3} \right) * \left( {\left( {2 * 4} \right){\bf{ + }}\left( {7{\bf{ - }}6} \right)} \right)\).

Now convert the expression in the infix form.

Since, the infix form of the expression is fully covered. So, \(\left( {\left( {9/3} \right) * \left( {\left( {2 * 4} \right){\bf{ + }}\left( {7{\bf{ - }}6} \right)} \right)} \right)\)is the infix form of expression.