# Why my solution TLE?

• Hello everyone! I wrote the following algorithm to check every root-to-leaf path and add valid ones to the answer vector. I think this is the best time complexity we could achieve, but why is my solution TLE?
Here's my code:

``````class Solution {
public:
vector<vector<int>> ans;
// vector to record current path
vector<int> st;

// this function goes from root to leaf to check every path
// node: which node we are processing
// des: the total value of tree path so far
void calc(TreeNode* node, int des)
{
// add this node's value to current path
st.push_back(node->val);
// calculate new value including this node
int total = des + node->val;
// if this is a leaf node
if (!node->left && !node->right)
{
// check whether this path is valid, if it is, add it to the answer vector
if (total == des)
ans.push_back(st);
return;
}
// otherwise this node is not a leaf node
// if left child exists, recursively check it
if (node->left)
calc(node->left, total);
// if right child exists, recursively check it
if (node->right)
calc(node->right, total);
// all children have been checked, so we remove this node'value from current path
st.pop_back();
}

vector<vector<int> > pathSum(TreeNode *root, int sum) {
ans.clear();
// if NULL is passed, just return empty vector
if (!root)
return ans;
// clear path vector
st.clear();
// check from root with initial sum 0
calc(root, 0);
return ans;
}
};``````

• i'm sorry. Here's my updated question.

• ``````        if (!node->left && !node->right)
{
// check whether this path is valid, if it is, add it to the answer vector
if (total == des)
ans.push_back(st);
// ERROR HERE
return;
}
``````

See the comment `ERROR HERE` line, when it is a leaf, this level of recursion will return from here, but your `st` do not pop, these may lead to large size of `st`, and I guess it take long time to push_back to `ans`, so it leads to TLE.

• Thanks a lot! It's just the problem. :-)

• And I just find another problem that I should compare "total" to "sum" but not to "des".

• An alternative to avoid pop_backs : Pass 'st' as an argument like

calc(TreeNode* node, int des, vector<int> v)

• pop may be more important reason

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