Could you please help me understand calculating the time and space complexity of the below function.
function(): Role: create vector of nodes at each levels
- create a queue.
- add the root
- copy the elements in the queue to the vector.
- traverse the vector and append the child(left & right) to the queue.
- repeat steps 3 & 4 until the queue is empty.
below is the code.
struct node {
int value;
struct node* p_left;
struct node* p_right;
};
void levels_list(struct node* p_btree) {
if(!p_btree) {
return ;
}
std::queue<struct node*> q;
std::vector<std::vector<struct node*> > v1;
q.push(p_btree);
bool choice = false;
while(!q.empty()) {
std::vector<struct node*> v;
while(!q.empty()) {
v.push_back(q.front());
q.pop();
}
for(int i = 0; i < v.size(); i++) {
if(v[i]->p_left) {
q.push(v[i]->p_left);
}
if(v[i]->p_right) {
q.push(v[i]->p_right);
}
}
v1.push_back(v);
v.clear();
}
}
I see that it is O(n^2), am I correct? There are two loops the first one is outer and the second one is the inner which pushes the elements into the vector from the queue.
Thanks
Aucun commentaire:
Enregistrer un commentaire