Time complexity calculation

Question

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:

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);
}

 

Comments

i think O(nlog(n))

---

I think O(lognlogn) would be more precise.

---

@amit, there are n nodes, on every node fun(left) and fun(right) calls. then it is (n. something)

---

@Shaik Masthan yes sir. We can write O(N*log N), but this is not the tightest upper bound because the height is not logN for each node.(here the height means that if we keep on going through the left of all nodes or right of all nodes, then the number of edges).

Answer: Tightest upper bound: O(N). Idea: Similar to Build heap. 

N: number of nodes.

---

@raja11sep

worst ans

---

I think it’s O(nlogn).
Is the code counting the number of nodes required to make the complete binary tree, a full binary tree?

---

No @adad20. This is a dummy function returning 0’s everywhere. We are interested in time complexity only.

---

@dd sir, what’s the time complexity then?

---

 I am getting theta(n) .

---

 

• 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)$.

---

@amitraj123 could you move your comment to answer ? Thanks

---

@amitraj123 Nice explaination 

---

Yes, sure @dd

---

Thanks @adad20

Answer 1

• 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)$.