# The Blind 75 Leetcode Series: Construct Binary Tree from Preorder and Inorder Traversal Photo by Chris Ried on Unsplash

Today, we are working on 105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree.

We are given 2 lists, one as the preorder traversal result of a tree and another as the inorder traversal result of the same tree. From these lists, we want to figure out what this tree looks like.

Some questions to ask are:

1. do we expect empty tree? (empty list)
2. are the values in the lists unique?

If the interviewers tell us that the tree always contains some nodes and the values are all unique, then we can start.

If you are not familiar with the pre-order and in-order traversals, basically pre-order traversal records the value first, then go left, then go right. It repeats the process at every node until we go through the entire tree. In-order traversal goes left first until it can’t. Then it records the value. Then it goes right. Once it goes to the next node, the process repeats.

Knowing these properties, we can say a few things:

1. the first value on the pre-order list is the root since pre-order traversal would record the value of the node first.
2. Knowing the value of root, since all values are unique, we can find the index of the value in the in-order traversal. Once we do, every value on the left of the root value is on the left side of the tree, and every value on the right belongs to the right side of the tree.
3. Now that we know the size of the tree on the left and on the right, we go back to pre-order list to slice the list. Since pre-order list would always have values from the left tree recorded first, if we know from the in-order list that there should be 3 nodes on the left tree, we can go ahead and slice the first 3 values from the pre-order list. These values should match. Try testing it.
4. We now have two sets of pre-order and in-order combos. We can feed it into the same function again to recursively build this tree.

To put everything into code, it looks like

`def buildTree(preorder, inorder):    if not preorder or not inorder:        return    root = TreeNode(preorder)    # find the index in the in-order list    idx = inorder.index(root.val)    # Slice the two lists into left-half and right-half. Knowing how to slide the lists is the key to this problem    left_preorder, right_preorder = preorder[1:idx+1], preorder[idx+1:]    left_inorder, right_inorder = inorder[:idx], inorder[idx+1:]    # recursively build the tree    root.left = self.buildTree(left_preorder, left_inorder)    root.right = self.buildTree(right_preorder, right_inorder)    return root`

What’s the time complexity here? We are going over the list recursively due to that `.index` operation, which takes linear time. We end up with O(N²) overall.

`def buildTree(preorder, inorder):    if not preorder or not inorder:        return    root = TreeNode(preorder)    # O(N)    idx = inorder.index(root.val)    left_preorder, right_preorder = preorder[1:idx+1], preorder[idx+1:]    left_inorder, right_inorder = inorder[:idx], inorder[idx+1:]    # recursion on O(N) makes it O(N^2)    root.left = self.buildTree(left_preorder, left_inorder)    root.right = self.buildTree(right_preorder, right_inorder)    return root`

Can we do better? What if we can eliminate the `.index`? That seems like the biggest bottleneck. If we can reduce that to O(1), we can reduce the overall time complexity to O(N). What type of “tracking” can give us O(1) read time? That sounds like a job for dictionary (hash table).

We start with doing one iteration through the entire inorder list to get the positions of each number. Then we do the same operation, except this time we find the idx through `hashtable.get(val)` . But to do that, we can’t just slice the list since it’ll change the index position. We will need to find a way to correctly track the in-order list’s index.

Instead of slicing the in-order list, we can use 2 pointers, left and right, to determine how we want to slice it without actually slicing the list.

We still want to get the first element of the pre-order list, so we want to pass in the pre-order list as part of the recursive function inputs as well. Then we need to pass in the tracker to determine the position of the elements in in-order list.

So our recursive functions will take…

`def recursive(left, right, preorder, inorder_index_map)`

The logic is almost the same inside the recursive. We first take the first element of the pre-order list. Since we are not slicing the list this time, we want to `pop` it from the list. `pop(0)` is a O(N) operation, so we want to make sure to convert the pre-order list to a `deque`, so we can do a O(1) `popleft()`.

We now just need to determine the correct value for `left` and `right` for each recursion.

Going back to the property of in-order list, we know that the left side of the target idx belongs to the left tree and the right side belongs to the right tree. So the `left` and `right` for the left tree is simply the same `left` and `inorder_index_map[root_val] — 1`, where `inorder_index_map` is the tracker we built and `root_val` is the value for the current node.

Similarly, for the right tree, we have the `right` being the same and `left` becomes `inorder_index_map[root_val] + 1`.

We can now put everything together.

`from collections import dequedef recursive(left, right, preorder, inorder_index_map):    # if there are no elements to construct the tree    if left > right:        return    root_val = preorder.popleft()    root = TreeNode(root_val)    root.left = recursive(left, inorder_index_map[root_val] - 1, preorder, inorder_index_map)    root.right = recursive(inorder_index_map[root_val] + 1, right, preorder, inorder_index_map)return rootdef buildTree(preorder, inorder]):    # so we can popleft with O(1)    preorder = deque(preorder)    # tracker for the value: idx of in-order list    inorder_index_map = {}    for index, value in enumerate(inorder):        inorder_index_map[value] = index    return recursive(0, len(preorder) - 1, preorder, inorder_index_map)`

And now, because we eliminated the `.index` and we did not add any more O(N) operation, we are now only looking at O(N) overall time complexity.

`def recursive(left, right, preorder, inorder_index_map):    if left > right:  # O(1)        return    root_val = preorder.popleft()  # O(1)    root = TreeNode(root_val)  # O(1)        root.left = recursive(left, inorder_index_map[root_val] - 1, preorder, inorder_index_map)    root.right = recursive(inorder_index_map[root_val] + 1, right, preorder, inorder_index_map)return rootdef buildTree(preorder, inorder]):    preorder = deque(preorder)    # building tracker: O(N)    inorder_index_map = {}    for index, value in enumerate(inorder):        inorder_index_map[value] = index    # overall recursive: O(N)    return recursive(0, len(preorder) - 1, preorder, inorder_index_map)`

That’s it! Another problem down. 