Time Complexity of building a height Balances tree

#1

what will be the time complexity of building a height balanced tree from an array and how?

#2

@dare_devil_007 the time complexity will be O(n), as you push on every node (or element) only once inside a queue.

#3

node* buildTreeFromArray(int* a, int s, int e) {

//BaseCase
if (s > e) {
	return NULL;
}

//Recursion
int mid = (s + e) / 2;
node* root = new node(a[mid]);

root->left = buildTreeFromArray(a, s, mid - 1);
root->right = buildTreeFromArray(a, mid + 1, e);

return root;

}
this is the code for it

#4

explain the time complexity

#5

complexity of function can be written as:
T(n) = 2xT(n/2) + O(1)
(as two calls on left and right half and also making node for mid)
on expansion for further n, it becomes O(n).

1 Like
#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.