1,189 views
0 votes
0 votes

A complete binary tree is a binary tree whose all levels except the last level are completely filled and all the leaves in the last level are all to the left side.

for example:

Full v.s. Complete Binary Trees


Now, assume that, each of the nodes in this tree is represented by a structure

struct node {
    char val;
    node* left;
    node* right
}


Find the time complexity of the following function:

 

int func(node* root) {
	if(root == NULL) return 0;

	node *L = root;
	int Lcnt = 0;
	while(L) {
		Lcnt++;
		L = L->left;
	}
	
	node *R = root;
	int Rcnt = 0;
	while(R) {
		Rcnt++;
		R = R->right;
	}
	
	if(Lcnt == Rcnt) return 0;

	return func(root->left) + func(root->right);
}

 

1 Answer

3 votes
3 votes
  • The best case for this question will be when we have perfect binary tree, where we will have Lcnt=Rcnt. Because of which, if condition will become true and there will be no need of recursive call, so in best case time complexity will be O(logn).
  • In worst case,  we can only have worst case in left subtree or right subtree because of complete binary tree property where Lcnt !=Rcnt but not on both side.
  • Lets suppose we have worst case in right subtree. then 

If condition will become false and recursive call execution will start. For left subtree root will become node B, and for node B function will return 0. now for right sub-tree Node C will be the root here again if condition will become false and Recursive call will get execute. 

Here at node C, we can only have worst case in left or right subtree but not in both. So we are eliminating every. same condition at every root node. 

Conclusion is- 

In worst case we can have logn nodes for which we need to traverse in the tree.In complete binary tree for traversal time comlexity will be O(logn). so for all logn nodes time complexity will be $O(lognlogn)$.

Related questions

1 votes
1 votes
0 answers
1
kartikeya2812 asked Jun 16, 2018
387 views
What will be the time complexity of the following algorithm ?A(n){if(n<=1) return 1;for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } }}
7 votes
7 votes
3 answers
2
bts asked May 29, 2018
1,827 views
Why is recursive equation of following code $T(n)=T(n/2)+O(1)$, not $T(n)=8*T(n/2)+O(1)$? int x=0; int A(n) { if(n==1) return 1; else { X+=8A(n/2)+n^3; } return X; }
5 votes
5 votes
0 answers
4
Mk Utkarsh asked Jan 9, 2018
407 views
T(n) $\leq$ T($\frac{n}{5}$) + T($\frac{7n}{10}$) + 15nT(n) $\leq$ 5 when n $<$ 6