The GATE Grind

GATE 2026 DA – Question 25

Programming, Data Structures and Algorithms · Stacks, queues, linked lists, trees and hash tables · 1 mark · Multiple select

You are given the following Pre-order and In-order traversals of a Binary Tree T with nodes E, F, G, P, Q, R, S.

Pre-order: P Q S E R F G

In-order: S Q E P F R G

Which of the following statements is/are true about the Binary Tree T?

  1. Node P is the root of T
  2. The Post-order traversal of T is: S E Q F G R P
  3. Node Q has only one child
  4. The left subtree of node R contains the node G

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Node P is the root of T; (B) The Post-order traversal of T is: S E Q F G R P

Explanation

The first node in the pre-order is the root, P. In the in-order, S, Q, E come before P (left subtree) and F, R, G come after it (right subtree). The left subtree has pre-order Q S E and in-order S Q E, so its root is Q with S on the left and E on the right. The right subtree has pre-order R F G and in-order F R G, so its root is R with F on the left and G on the right. The tree is $P(Q(S, E), R(F, G))$, so the post-order is S E Q F G R P. Q has two children and G is in the right subtree of R, so C and D are false.