educative.io

Why time complexity O(n^2)?

Courses
,
#1

regarding c++ solution, I have a vector of int, and each node I push the root->val and then recurse to the root->left and root->right

and then I pop_back on backtracking, so why the time complexity is O(n^2)? while at each node I push once and pop once

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5714315743068160

1 Like
#2

There is another vector<vector<int>> which stores all the paths that satisfy the condition. Once a valid path is found we have to push it to this vector which also takes O(N) times. In the worst-case scenario, every path from the root to a leaf could be a valid path, so an upper bound of N^2 is a valid bound.

#3

Hope it’s clear now. If there is still confusion we can discuss it further.

1 Like
#4

Thanks so much!