Interview Question for Software Development Engineer at Microsoft:

This is a cool question.

A Recursion function with input paramters as preOrder[] and inOrder[]
stop if preOrder is null or preOrder length is 0

Create In Order Elements for Left Side
Create In Order Elements for Right Side

Create Pre Order Elements for Left Side
Create Pre Order Elements for Right Side

Create the node and using recursion assign the value to Left and Right nodes

I guess the key here it to ask what can be considered for reference when creating the tree
for instance
PreOrder 1,2,4,5,3,6,7 <-- First element is the parent for the split sub array
InOrder 4,2,5,1,6,3,7 <-- the parent element is in between the left and right arrays

if we consider unique values this approach can work or we can change it to use the pointer or reference for
each node, I mean if the array has the value and the pointer I guess those are the keys to identify the solution.
Correctme if I'm wrong but how can we rebuilt a tree with a specific structure if all elements are the same.

Here it's my code, I'm using List<int> but with some refactoring we could avoid then and use start and end indexes.

  public TreeNode FromInOrderAndPreOrder(int[] preOrder, int[] inOrder)
        {
            if (preOrder == null || preOrder.Length == 0)
                return null;

            int nodeValue = preOrder[0];
            Dictionary<int, int> rightInOrderDic = new Dictionary<int, int>();

            int index = 0;
            // Create In Order Elements for Left Side
            List<int> leftInOrder = new List<int>();
            for (; index < inOrder.Length; index++)
            {
                if (inOrder[index] == nodeValue)
                    break;
                leftInOrder.Add(inOrder[index]);
            }
            // Create In Order Elements for Right Side
            List<int> rightInOrder = new List<int>();
            for (index = index + 1; index < inOrder.Length; index++)
            {
                rightInOrderDic.Add(inOrder[index], inOrder[index]);
                rightInOrder.Add(inOrder[index]);
            }

            // Create Pre Order Elements for Right Side
            List<int> leftPreOrder = new List<int>();
            int start = 1;
            for (; start < preOrder.Length; start++)
            {
                if (rightInOrderDic.ContainsKey(preOrder[start]))
                    break;
                leftPreOrder.Add(preOrder[start]);
            }
            // Create Pre Order Elments for Left Side
            List<int> rightPreOrder = new List<int>();
            for (; start < preOrder.Length; start++)
            {
                rightPreOrder.Add(preOrder[start]);
            }

            TreeNode newNode = new TreeNode();
            newNode.Data = nodeValue;

            newNode.Left = FromInOrderAndPreOrder(leftPreOrder.ToArray(), leftInOrder.ToArray());

            newNode.Right = FromInOrderAndPreOrder(rightPreOrder.ToArray(), rightInOrder.ToArray());

            return newNode;

        }