# Leetcode: Reconstruct binary tree

Given two lists of a `preorder` and `inorder`, create a tree and return the `root` node.

The problem is not so obvious at first. If the preorder list would also contain `null` values for the places where the tree does not contain nodes, we could simply iterate over this list and reconstruct the tree from there. But since the `null` values are missing, we also need to take a look at the `inorder` list. We know about the `preorder` list that the traversal is as follows: `NLR`. This means that first the node is visited, then we go recursively to the left, and then recursively to the right. For `inorder` it is `LNR`: We go recursively to the left, then output the node, and finally go to the right. Because of those properties, we know that the `root` node is the first one in the `preorder` list. Since there is only one `root` node, we know that the next node will be in the next level. We don’t know, from looking at the `preorder` list, if the next child node is to the left or right. To figure this out, we need to look at the `inorder` list. If the node is to the left of our current element, know that it must be the immediate child to the left. We then determine the position of the node in the `inorder` list and pass it recursively to the same method. If it is to the right, we remove the left prefix from the `preorder` list, add it as a right node, and pass in the left and right lists to the recursive function. Finally, we return the `root` node.
Runtime: 722 ms, faster than 5.01% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal. Memory Usage: 89.2 MB, less than 5.37% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.