Hi, here’s your problem today. This problem was recently asked by Microsoft:

You are given the preorder and inorder traversals of a binary tree in the form of arrays. Write a function that reconstructs the tree represented by these traversals.

Example: Preorder: [a, b, d, e, c, f, g] Inorder: [d, b, e, a, f, c, g]

The tree that should be constructed from these traversals is:

```
a
```

/

b c
/ \ /

d e f g

Here’s a start:

from collections import deque

class Node(object):
def **init**(self, val):
self.val = val
self.left = None
self.right = None

def **str**(self):
q = deque()
q.append(self)
result = ‘’
while len(q):
n = q.popleft()
result += n.val
if n.left:
q.append(n.left)
if n.right:
q.append(n.right)

```
return result
```

def reconstruct(preorder, inorder):

# Fill this in.

tree = reconstruct([‘a’, ‘b’, ‘d’, ‘e’, ‘c’, ‘f’, ‘g’], [‘d’, ‘b’, ‘e’, ‘a’, ‘f’, ‘c’, ‘g’]) print tree