How to create a binary tree with the traversals given?

Question

Okay, so say that we are given two lists: the pre-order traversal values of a binary tree, and the in-order traversal values given in a list. Now, I need to create a tree (in list form e.g. [1, [2, [2, None, None], None], [1, None, None]]). I can tell the root value and the number of elements in each side of the tree from the traversal values, but I'm kind of confused as to how to create the tree itself. Is recursion a good idea for this question, seeing as how we're creating subtrees within the main tree?

This can't be done with classes, either. It has to be a function. Classes would have made it much easier, but I'm not supposed to use them.

Answer 1

This may be helpful.

Summary:
With the pre-order traversal [x1,…,xn] and the in-order traversal [z1,…,zn], you can rebuild the tree as follows:

The root is the head of the pre-order traversal x_1. Let k be the index such that z_k=x1. Then [z_1,…,z_k−1] is the in-order traversal of the left child and [z_k+1,…,z_n] is the in-order traversal of the right child. Going by the number of elements, [x_2,…,x_k] is the pre-order traversal of the left child and [x_k+1,…,x_n] that of the right child. Recurse to build the left and right subtrees.