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?
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).
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
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.
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.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.