# Hashmap optimisation results in TLE

Solution for Hashmap optimisation results in TLE
is Given Below:

I attempted the below problem to construct Binary Tree given the Preorder and Inorder Traversal arrays, Since the construction of left and right subtree of any given node requires finding the position of that node in Inorder Traversal array which renders an Overall Time Complexity of O(n^2) to solution .

I attempted to optimize the solution by hashing the Inorder array values with their indices ,However the solution showed Time Limit Exceeded in the last of 203 test cases.

My question is since searching in Hashmap (Unordered map in C++) is on average O(1) how can an optimization further worsen the run time of the solution ?
Thank you

[My Hashmap Optimized Solution]

``````class Solution {
public:
TreeNode * helper(vector<int> preorder,int pstart,vector<int> &inorder,int istart,int iend, unordered_map<int, int> umap)
{
if(preorder.size()-1<pstart||iend<istart) return NULL;

TreeNode * root = new TreeNode(preorder[pstart]);

int i = umap[preorder[pstart]];

root->left =helper(preorder,pstart+1,inorder,istart,i-1,umap);
root->right =helper(preorder,pstart+(i-istart)+1,inorder,i+1,iend,umap);

return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
int n = preorder.size();
unordered_map<int, int> umap;
for (int i = 0; i < inorder.size(); i++)
{
umap[inorder[i]]=i;
}
return helper(preorder,0,inorder,0,n-1,umap);
}
};
``````