Question 8136 – Data-Structures
April 17, 2024Question 8518 – Data-Structures
April 17, 2024Question 8138 – Data-Structures
Consider the following New-order strategy for traversing a binary tree:
- Visit the root;
- Visit the right subtree using New-order;
- Visit the left subtree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 – 2 ˆ 6 7 * 1 + – is given by:
Correct Answer: C
Question 33 Explanation:
New Order strategy: Root, Right, Left.
Given Reverse Polish Notation as:
3 4 * 5 – 2 ^ 6 7 * 1 + –
We know Reverse Polish Notation takes Left, Right, Root.
So the expression tree looks like
From the tree, we can write the New Order traversal as: Root, Right, Left.
– + 1 * 7 6 ^ 2 – 5 * 4 3
Given Reverse Polish Notation as:
3 4 * 5 – 2 ^ 6 7 * 1 + –
We know Reverse Polish Notation takes Left, Right, Root.
So the expression tree looks like
From the tree, we can write the New Order traversal as: Root, Right, Left.
– + 1 * 7 6 ^ 2 – 5 * 4 3
+ – 1 6 7 * 2 ˆ 5 – 3 4 *
– + 1 * 6 7 ˆ 2 – 5 * 3 4
– + 1 * 7 6 ˆ 2 – 5 * 4 3
1 7 6 * + 2 5 4 3 * – ˆ –