# O(n^2) solution submitted but when I use a map to do it in O(n), it times out on the last case.

• ``````TreeNode* buildTree_util(vector<int>& preorder, int &start, vector<int>& inorder, int left, int right, unordered_map<int, int> hash_map)
{
if (left > right)
return NULL;
TreeNode *root = new TreeNode(0);
int node = preorder[start++];
root->val = node;
/*
int i = left;
for (; i < right; i++)
{
if (inorder[i] == node)
break;
}
*/
int i;
if (left == right)
i = left;
else
i = hash_map[node];
root->left = buildTree_util(preorder, start, inorder, left, i - 1, hash_map);
root->right = buildTree_util(preorder, start, inorder, i + 1, right, hash_map);
return root;

}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int start = 0;
unordered_map<int, int> hash_map;
int count = 0;
for (int num: inorder)
hash_map[num] = count++;
return buildTree_util(preorder, start, inorder, 0, inorder.size() - 1, hash_map);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.