lundi 26 janvier 2015

time and space complexity creating vector of elements at each levels of a binary tree(NON-BST)

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



  1. create a queue.

  2. add the root

  3. copy the elements in the queue to the vector.

  4. traverse the vector and append the child(left & right) to the queue.

  5. 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