+1 vote
in Data Structures & Algorithms I by (110k points)
The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be ________

(a) T Q R S O P

(b) T O Q R P S

(c) T Q O P S R

(d) T Q O S P R

This interesting question is from Binary Trees topic in division Binary Trees of Data Structures & Algorithms I

I have been asked this question by my school principal while I was bunking the class.

1 Answer

+1 vote
by (672k points)
selected by
Best answer
Correct answer is (c) T Q O P S R

For explanation: The last, second last nodes visited in post-order traversal are root and it’s right child respectively. Option T Q R S O P can’t be a pre-order traversal, because nodes O, P are visited after the nodes Q, R, S. Option T O Q R P S, can’t be valid, because the pre-order sequence given in option T O Q R P S  and given post-order traversal creates a tree with node T as root and node O as left subtree. Option T Q O P S R is valid. Option T Q O S P R is not valid as node P is visited after visiting node S.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.