Discussion
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:
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.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development