Construct a binary tree from its in-order and pre-order traversals

This is a simple guide on how to construct a binary tree from its in-order and pre-order traversals.

As a remainder,

In-Order : Left -> Root -> Right

Pre-Order : Root -> Left -> Right

Consider the following in-order and pre-order traversals of a binary tree

In-Order : 4, 2, 5, 1, 6, 3, 7

Pre-Order : 1, 2, 4, 5, 3, 6, 7

The root is simply the first element of the pre-order traversal

Find the root in the in-order traversal and split the traversal into 2 halves of size 3 each. ie., In-order traversal of left and right sub-trees.

Since we just found that the size of in-order traversal of left sub-tree is 3, we can split the pre-order traversal accordingly in to left and right.

So the 3 elements immediately following the root in the pre-order form the pre-order of the left sub-tree and the rest are the pre-order of the right sub-tree.

Now, consider the left in-order and pre-order traversals and repeat the same process of finding the root.

Again split it into left and right in-order and pre-order traversals

Now, there is only 1 element in in-order and pre-order each. So just add them as leaf nodes.

Repeat for the element 5

Now the left sub-tree of root element 1 is complete. Repeat the same process for the right sub-tree.

The completed tree would look something like this

Try writing code for this Leetcode Problem using the methods we just learned