Consider the following data and specify which one is Preorder Traversal Sequence, Inorder and Postorder sequences. S1: N, M, P, O, Q S2: N, P, Q, O, M S3: M, N, O, P, Q

Correct Answer: S1 is inorder, S2 is postorder and S3 is preorder
Preorder traversal starts from the root node and postorder and inorder starts from the left child node of the left subtree. The first node of S3 is different and for S1 and S2 it’s the same. Thus, S3 is preorder traversal and the root node is M. Postorder traversal visits the root node at last. S2 has the root node(M) at last that implies S2 is postorder traversal. S1 is inorder traversal as S2 is postorder traversal and S3 is preorder traversal. Therefore, S1 is inorder traversal, S2 is postorder traversal and S3 is preorder traversal.