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