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:
GATE CS - 2016,
Answer: C
The New-order traversal is - + 1 * 7 6 ^ 2 - 5 * 4 3.
Build the tree from the postfix expression 3 4 * 5 - 2 ^ 6 7 * 1 + -: it is ((3 * 4) - 5) ^ 2 - ((6 * 7) + 1). The root is the last operator, -, with left subtree ((3*4)-5) ^ 2 and right subtree (6*7)+1.
New-order visits root, then right subtree, then left subtree, recursively:
- Root: -
- Right subtree
(6*7)+1: +, then its right child 1, then its left subtree * 7 6 (root, right, left). - Left subtree: ^, then its right child 2, then its left subtree -, 5, then * 4 3.
This gives - + 1 * 7 6 ^ 2 - 5 * 4 3. New-order is exactly the reverse of postfix order, which is a quick check: reverse 3 4 * 5 - 2 ^ 6 7 * 1 + - and you get the same string. The option with * 6 7 and * 3 4 visits the left child before the right in the inner subtrees, and the other two options start with the wrong node.
Please log in or register to report this question.
