Question Details

You are given the following preorder and In-order traversal of binary Tree T

with nodes E, F, G, P, Q, R, S

Preorder : P, Q, S, E, R, F, G

Inorder: S, Q, E, P, F, R, G


Which of the following statements is/are true about the binary True T?

Options

A

Node Q has only once child

B

Post order traversal SEQFGRP

C

P is the root of T

D

The left subtree of node R contains node G

Show Answer
Correct Answer
B Post order traversal SEQFGRP
C P is the root of T

Solution :

The correct options are:
"P is the root of T" and "Post order traversal SEQFGRP".

To understand why these options are correct, we can reconstruct the binary tree T step-by-step using the given preorder and inorder traversals.

Step 1: Identifying the root of the tree
In a preorder traversal (Root, Left, Right), the first node visited is always the root.
Given Preorder: P, Q, S, E, R, F, G.
Therefore, P is the root of T. This directly confirms one of the correct options.

Step 2: Partitioning the Inorder traversal
In an inorder traversal (Left, Root, Right), all nodes to the left of the root belong to its left subtree, and all nodes to the right belong to its right subtree.
Given Inorder: S, Q, E, P, F, R, G.
Since P is the root:
- The left subtree contains nodes: {S, Q, E}
- The right subtree contains nodes: {F, R, G}

Step 3: Reconstructing the Left Subtree
For the left subtree nodes {S, Q, E}:
- The preorder segment is: Q, S, E. The first element is Q, so Q is the root of the left subtree.
- The inorder segment is: S, Q, E. Since Q is the root, S is in its left subtree, and E is in its right subtree.
- Thus, Q has two children: a left child S and a right child E. (This shows that the option "Node Q has only one child" is false).

Step 4: Reconstructing the Right Subtree
For the right subtree nodes {F, R, G}:
- The preorder segment is: R, F, G. The first element is R, so R is the root of the right subtree.
- The inorder segment is: F, R, G. Since R is the root, F is in its left subtree, and G is in its right subtree. (This shows that the option "The left subtree of node R contains node G" is false, as G is in the right subtree of R).

Step 5: Structure of the Binary Tree T
The final structure of the tree is:
- Root: P
- Left Child of P: Q
- Right Child of P: R
- Left Child of Q: S
- Right Child of Q: E
- Left Child of R: F
- Right Child of R: G

Step 6: Finding the Postorder Traversal
A postorder traversal visits the tree in the order: Left Subtree, Right Subtree, Root.
- For the left subtree rooted at Q, the postorder traversal is: S, E, Q.
- For the right subtree rooted at R, the postorder traversal is: F, G, R.
- Combining these with the root P at the end, the postorder traversal of T is:
S, E, Q, F, G, R, P (or SEQFGRP).

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: