GATE CS Mastery
Cheat sheets

GATE CS 2016 Set 2 · Data Structures

Question 46

MCQPrinted as CS Q.362 marksWrong answer: −2/3Medium (estimate)

Question

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 + −3\ 4\ *\ 5\ -\ 2\ \text{\^{}}\ 6\ 7\ *\ 1\ +\ -

is given by:

Choose one option
Official answer and solution
Official answer
C
From
Official GATE 2016 answer key

Solution

Construct the expression tree from the reverse Polish string and perform the New-order traversal (Root, Right, Left).

Given Reverse Polish (postfix) expression:

3 4 ∗ 5 − 2 ˆ 6 7 ∗ 1 + −3\ 4\ *\ 5\ -\ 2\ \text{\^{}}\ 6\ 7\ *\ 1\ +\ -

Construct the expression tree step-by-step using a stack:

  1. 3, 4, *: Subtree T1=(∗,3,4)T_1 = (*, 3, 4)
  2. T_1, 5, -: Subtree T2=(−,T1,5)=(−,(∗,3,4),5)T_2 = (-, T_1, 5) = (-, (*, 3, 4), 5)
  3. T_2, 2, ^: Subtree T3=(ˆ,T2,2)=(ˆ,(−,(∗,3,4),5),2)T_3 = (\text{\^{}}, T_2, 2) = (\text{\^{}}, (-, (*, 3, 4), 5), 2)
  4. 6, 7, *: Subtree T4=(∗,6,7)T_4 = (*, 6, 7)
  5. T_4, 1, +: Subtree T5=(+,T4,1)=(+,(∗,6,7),1)T_5 = (+, T_4, 1) = (+, (*, 6, 7), 1)
  6. T_3, T_5, -: Root is - with left child T3T_3 and right child T5T_5.

Apply New-order traversal: [Root, New-order(Right), New-order(Left)]:

  1. Root: -
  2. New-order on Right Subtree T5=(+,(∗,6,7),1)T_5 = (+, (*, 6, 7), 1):
    • Visit root: +
    • Right child: 1
    • Left child T4=(∗,6,7)T_4 = (*, 6, 7):
      • Visit root: *
      • Right child: 7
      • Left child: 6
        Right traversal sequence: + 1 * 7 6
  1. New-order on Left Subtree T3=(ˆ,(−,(∗,3,4),5),2)T_3 = (\text{\^{}}, (-, (*, 3, 4), 5), 2):
    • Visit root: ^
    • Right child: 2
    • Left child T2=(−,(∗,3,4),5)T_2 = (-, (*, 3, 4), 5):
      • Visit root: -
      • Right child: 5
      • Left child T1=(∗,3,4)T_1 = (*, 3, 4):
        • Visit root: *
        • Right child: 4
        • Left child: 3
          Left traversal sequence: ^ 2 - 5 * 4 3

Concatenating Root + Right + Left:

−+1∗76 ˆ 2−5∗43- + 1 * 7 6 \text{ \^{} } 2 - 5 * 4 3

This matches option (C).

Final answer

C

Common trap

Visiting left before right (standard pre-order) instead of the defined New-order (right before left).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2016 Computer Science and Information Technology (CS) Session 2
Question
46 of 65, printed as CS Q.36
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.