Let QSPTRU and PQSRTU are in-order traversal and pre-order traversal respectively for a given binary tree T. What will be the post-order traversal T?

Question

Accepted Answer

The correct option is (3):
The process of determining the post-order traversal (Left, Right, Node) from the given in-order (Left, Node, Right) and pre-order (Node, Left, Right) traversals involves a recursive breakdown of the binary tree structure. The **pre-order traversal (PQSRTU)** immediately identifies the root of the entire tree: **P**. We then use this root to divide the **in-order traversal (QSPTRU)** into its Left and Right subtrees. All nodes to the left of P in the in-order sequence form the Left Subtree (QS), and all nodes to the right form the Right Subtree (TRU). The post-order traversal is then constructed by first listing the post-order of the Left Subtree, followed by the post-order of the Right Subtree, and finally the main root, P.

The post-order of the Left Subtree (QS) is **SQ** (S is the right child of Q), and the post-order of the Right Subtree (TRU) is **TUR** (T is the left child of R, and U is the right child of R). Combining these results with the root P gives the final post-order traversal: **S Q T U R P**.

The incorrect option is (1):
Option (1) SQUTRP incorrectly places the Right Subtree nodes. The correct post-order for the Right Subtree (T, R, U) must place the root (R) at the end of its sequence, resulting in T U R. The sequence U T R in this option is incorrect, as it implies U is the root of the T, R, U subtree, which contradicts the given pre-order sequence R T U. Traversal order must consistently follow the L-R-N rule for post-order.

The incorrect option is (2):
Option (2) QSUTRP places the root of the entire tree (P) at the end, which is a requirement for post-order, but it incorrectly orders the nodes within the Left Subtree. The post-order for the Left Subtree (Q, S) should be S Q, not Q S. A Q S ordering suggests a pre-order traversal for that subtree or an incorrect L-N-R/N-L-R rule was applied.

The incorrect option is (4):
Option (4) QSUTPR is incorrect because it fails to place the main root of the entire tree, P, as the *very last* element. In any complete post-order traversal (Left, Right, Node), the final element must be the root of the whole tree. Placing R before P violates the fundamental rule of post-order traversal. R is the root of the Right Subtree, not the main tree.