Question

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.

Answer 1

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.