Data Structures and Algorithms - Old Questions

3. A binary tree T has 12 nodes. The in-order and pre-order traversals of T yield the following sequence of nodes:

In-order : VPNAQRSOKBTM

Pre-order : SPVQNARTOKBM

Construct the Binary tree T showing each step. Explain, how you can arrive at solution in brief?

Given,

In-order : VPNAQRSOKBTM

Pre-order : SPVQNARTOKBM

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘S’ is root for given sequences. By searching ‘S’ in In-order sequence, we can find out all elements on left side of ‘S’ are in left subtree and elements on right are in right subtree. So we know below structure now.

Among VPNAQR, P appears first in pre-order so it is root of left subtree. 

Now, we recursively follow above steps for left subtree:

_______________

Among OKBTM, T appears first in pre-order so it is root of right subtree.

Now, we recursively follow above steps for right subtree:

_______________

Which is the required binary tree.