 Given two integer arrays `preorder` and `inorder` containing the preorder and inorder traversals of a binary tree, construct the binary tree, and return its root. The values in the traversals will all be unique. Example: We want to create a function that takes in and , and returns the root node of the tree. `` buildTree(preorder, inorder) `` s2 To make this function recursive, should call itself to construct the and nodes. You can draw the recursion visually as: The next thing we have to do is 

Tree from Preorder and Inorder Traversal



-----problem-----


Given two integer arrays `preorder` and `inorder` containing the preorder and inorder traversals of a binary tree, construct the binary tree, and return its root. The values in the traversals will all be unique.

    \b{Example:} 
    $$
    \begin{align*}
    \texttt{preorder }&\texttt{= [3, 2, 9, 1, 4, 5]} \\
    \texttt{inorder }&\texttt{= [9, 2, 1, 3, 4, 5]}
    \end{align*}
    $$
    \image{0, 220}

-----solution-----



We want to create a function that takes in $\text{preorder}$ and $\text{inorder}$, and returns the root node of the tree.
``
buildTree(preorder, inorder)
``

\s2

To make this function recursive, $\tt buildTree$ should call \i{itself} to construct the $\texttt{root.left}$ and $\texttt{root.right}$ nodes. You can draw the recursion visually as:

\image{1, 200}

The next thing we have to do is figure out what $\small \text{pL, iL, pR, iR}$ and
$\text{v}$ are. Here's a visual of how to do this - the idea is to look back and forth between the two arrays until we find everything:
\image{3, 160}


We have everything we need for the recursion. Here's the recursion:
``
buildTree(preorder, inorder) = (
    v = preorder[0]
    i = inorder.index(v) # finds index of root in `inorder`

    # finds traversals of children as above
    iL = inorder[0:i]
    iR = inorder[i+1:]
    pL = preorder[1: i+1]
    pR = preorder[i+1:]

    # sets and returns root
    root = TreeNode(v)
    root.left = buildTree(pL, iL)
    root.right = buildTree(pR, iR)
    return root
)

``



\s3

The recursion calls itself on smaller and smaller arrays, since it keeps splicing the input. The smallest case is when we get to two empty arrays - at this point, it means we're building a null node. (Note that the arrays will always be the same size). 


``
buildTree([], []) = None
``




\s4

To code this, we just have to do is combine the recursion and base case:

\answer

\tc $O(n^2)$. We visit each of the $n$ nodes once. At each node, we create the arrays $\tt pL, pR, iL, iR$  which all take $O(n)$ operations. We also call $\texttt{inorder.index(v)}$ which is also $O(n)$. Adding this all up, the total operations per function call is $O(5n)$ and we call the function $n$ times. This means the total time is $O(5n)*n = O(n^2)$. 

\sc $O(n^2)$. The 
Call Stack grows to the height of the tree, which is $n$. Each call in the Call Stack needs to remember its inputs, which are both size $O(n)$ arrays. This gives $O(n^2)$ memory.

This solution should pass in an interview (I got a FAANG job with it), but you can make some optimizations. If you're curious what they are, see the spoiler below.

\spoiler{


One problem is that it takes  $O(n)$ time to call $\texttt{inorder.index()}$, which is slow. We can instead compute all the results in a HashMap before we start, which means we don't have to call $\texttt{inorder.index()}$, and can instead just look the results up in $O(1)$ time.


Another problem is that the function has arrays as inputs, which takes up $O(n)$ memory. We can instead use numbers as inputs, which only use $O(1)$ memory. 

Here's how you do both of these:


```
def buildTree(preorder, inorder):

    # HashMap that takes in a value and gives an index 
    indexOfVal = {val:i for i,val in enumerate(inorder)}
    
    # function takes in numbers
    # numbers represent start and end indexes of the arrays
    def buildTreeIdxs(p0, p1, i0, i1):
        # base case
        if p0 == p1 and i0 == i1:
            return None

        # recursion
        v = preorder[p0]
        i = indexOfVal[v] - i0 # index measured from i0

        root = TreeNode(v)
        root.left = buildTreeIdxs(p0 + 1, p0 + i+1, i0, i0 + i)
        root.right = buildTreeIdxs(p0 + i+1, p1, i0 + i+1, i1)

        return root
    return buildTreeIdxs(0, len(preorder), 0, len(inorder))
```

\tc $O(n)$. We need to go through all the nodes in the tree.

\sc $O(n)$. The 
\link{
/coding/109,
Call Stack
} still grows to a height of n, but now each call in the call stack needs to store indices, which are just O(1) memory. This gives O($n$) memory.

}



Recursion

Tree from Preorder and Inorder Traversal