The space complexity is not O(log n) as BFS traverses the tree level by level, and not store elements by node's path like DFS At one time, max queue size (space needed) will be the max width of the tree, that is O(n/2 + 1) indicating last level of complete binary tree, which is simplified to O(n)
@@kevinjmathews2964 leetcode runtime is biased so I wouldn't be too reliant on it - as long as you can explain your solution in great detail with runtime you should be fine
Key is once you find a null node , you mustn't get any other non null node from the tree..if there is the return false.
Beautiful solution, I write 1 page long of code for this problem ...
Very clear:) even for someone with very little dsa experience, thanks!
You make it very easy to understand. So, when I am stuck on a problem. I go to your channel
Still making great videos, keep up the great work. I like that I can pretty much solve it just from your explanation before you even show the code.
My solution was similar in principle but a lot longer. Thanks for sharing this, very succinct!
What does he use for drawing? How do you draw in the same page as the question? Do you use an iPad to draw and write?
I think he uses paint, he must have taken a screen grab of the problem and paste it on the canvas
very needed. thank you!
Amazing explanation 👍
This is such a great solution
Thanks for the video
so brilliant... I just came out with some bad methods and messy code
dhanyavad ji 🟠⚪🟢
that was beautiful
super smarrt!
Could someone help me understand why the space complexity not O(log n) which is the height of the three?
The space complexity is not O(log n) as BFS traverses the tree level by level, and not store elements by node's path like DFS
At one time, max queue size (space needed) will be the max width of the tree, that is O(n/2 + 1) indicating last level of complete binary tree, which is simplified to O(n)
Amazing explanation..._/\_
C++ implementation
bool isCompleteTree(TreeNode* root) {
bool flag = false;
queue q;
q.push(root);
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
if (!node) {
flag = true;
} else {
if (flag) {
return false;
}
q.push(node->left);
q.push(node->right);
}
}
}
return true;
}
You dont need inner for loop for this use case.
@@mubeenkodvavi6308 yeah not required. But for some reason leetcode gives a better runtime with the for loop (at least for python that's the case).
@@kevinjmathews2964 leetcode runtime is biased so I wouldn't be too reliant on it - as long as you can explain your solution in great detail with runtime you should be fine