# 0(n log n) solution in cpp

#1
``````/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

vector<int> FindMax(vector<int> &A,int l,int r)
{
int maxi=INT_MIN;
int j=0,i;
for( i=l;i<=r;i++)
{
if(maxi<=A[i])
{
maxi = A[i];
j=i;
}
}

vector<int> v(2,0);
v[1]=maxi;
v[0]=j;

return v;
}

TreeNode* Tree(vector<int> &A,int l ,int r)
{
vector<int> v = FindMax(A,l,r);
int mid = v[0];
TreeNode* t = new TreeNode(v[1]);
t->left=t->right=NULL;
if(mid-1>=l)
t->left=Tree(A,l,mid-1);
if(mid+1<=r)
t->right=Tree(A,mid+1,r);

return t;
}
TreeNode* Solution::buildTree(vector<int> &A) {
return Tree(A,0,A.size()-1);
}``````

#2

how come it is O(nlogn).Is its time complexity not O(n^2)

#3

It breaking problem into two subset

#4

Use master than to calculate required complexity.

#5

But it doesnâ€™t ensure to divide the array in two equal half. so In worst case its complexity will be O(n^2).