David has generated a random $21-$node full binary tree, in which each node is labeled with a consonant in the English alphabet $($Y is considered a consonant for this tree$).$ Unfortunately, the only record that David wrote down for this tree were the following traversals of the nodes:

Preorder: XNTSWDFBKYGVCLHRQMJPZ

Postorder: WDSBKFTVCGLYNQMRPZJHX

The goal of this problem is to figure out the inorder traversal of David's tree, given the other two traversals above.

$($Your answers to the following questions should be strings of capital letters, spaces will be ignored.$)$

What is the root of David's tree? $($Where does the root appear in the postorder traversal?$)$

Root $=$

X

What is the preorder traversal of the left subtree of the root? $($This should be a substring of the preorder traversal of the entire tree.$)$

What is the preorder traversal of the right subtree of the root? $($This should be a suffix of the preorder traversal of the entire tree.$)$

What is the postorder traversal of the left subtree of the root?

What is the postorder traversal of the right subtree of the root?

Now we have two recursive subproblems:

Given preorder and postorder traversals of the left subtree, what is its inorder traversal?

Given preorder and postorder traversals of the right subtree, what is its inorder traversal?

Combining the answers to these recursive subproblems with the root should give you the answer to the final question: What is the inorder traversal of David's tree?