Please solve this Q

Question

What is the time complexity to construct a binary tree when inorder and preorder traversal of the tree is given?

1. O(n) 2.O(n log n) 3. O(n2) 4.O(n2 log n)

Answer 1

O(N)

Comments

But ans is O(n2)

---

http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

this solution is in order O(n^2).

optimize this solution by

create hash for each value  of inorder sequence and utilize it in search function as it can search inO(1)