# C++ why insert() is much slower than push_back() + reverse()

• ``````class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
//return solution1(root);
return solution2(root);
}
private:
vector<vector<int>> v;
vector<vector<int>> solution1(TreeNode *root){
subSol2(root, 0);
return v;
}
void subSol1(TreeNode *root, int depth){
if(!root) return;
if(v.size() <= depth) v.insert(v.begin(), vector<int>());
v[v.size() - 1 - depth].push_back(root->val);
subSol1(root->left, depth + 1);
subSol1(root->right, depth + 1);
vector<vector<int>> solution2(TreeNode *root){
subSol2(root, 0);
reverse(v.begin(), v.end());
return v;
}
void subSol2(TreeNode *root, int depth){
if(!root) return;
if(v.size() <= depth) v.push_back(vector<int>());
v[depth].push_back(root->val);
subSol2(root->left, depth + 1);
subSol2(root->right, depth + 1);
}
};
``````

solution1 takes up to 56ms but solution2 only uses 8 ms. Why insert() is so much slower than push_back() + reverse function?

• /**

• Definition for a binary tree node.

• struct TreeNode {

• ``````int val;
``````
• ``````TreeNode *left;
``````
• ``````TreeNode *right;
``````
• ``````TreeNode(int x) : val(x), left(NULL), right(NULL) {}
``````
• };
/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode
root) {
vector<vector<int>> res;
if(!root) return res;
vector<TreeNode*> nodes;
nodes.push_back(root);

`````` while(!nodes.empty())
{
res.push_back(std::vector<int>());
vector<TreeNode*> tmp;
for(int i = 0 ; i < nodes.size() ; ++i)
{
res.back().push_back(nodes[i]->val);
if(nodes[i]->left)
tmp.push_back(nodes[i]->left);
if(nodes[i]->right)
tmp.push_back(nodes[i]->right);
}
tmp.swap(nodes);
}

for(int i = 0 ; i < res.size()/2 ; ++i)
{
res[i].swap(res[res.size() - 1 - i]);
}
``````

}
};

• sorry, I don't get your point. can you please explain a little bit?

• I have same problem, can anybody explian why?

• I have same problem, can anybody explian why?

• Read documentation for `insert` and `push_back`?

Inserting at the start takes linear time, appending averages constant time.

• insert at the beginning of vector will shift all the subsequent elements, so insert N times, it takes O(N^2) time complexity. However, append to the end, insert N times, the amortized time complexity is O(N) and reverse will take O(N) as well.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.