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

abcdefg