@TechDose There can be more optimization done for space complexity as here we are using recursion so the stack size will be Theta(N) Here is the sample implementation: ``` class Solution { // Return tree depth in O(d) time. public int computeDepth(TreeNode node) { int d = 0; while (node.left != null) { node = node.left; ++d; } return d; } // Last level nodes are enumerated from 0 to 2**d - 1 (left -> right). // Return True if last level node idx exists. // Binary search with O(d) complexity. public boolean exists(int idx, int d, TreeNode node) { int left = 0, right = (int)Math.pow(2, d) - 1; int pivot; for(int i = 0; i < d; ++i) { pivot = left + (right - left) / 2; if (idx right). // Perform binary search to check how many nodes exist. int left = 1, right = (int)Math.pow(2, d) - 1; int pivot; while (left
This video is a Very helpful to understand problem of complete binary tree.. I'm saying thanking you sir most 😊 .. to make a such beautiful explanation
So basically what we are doing is T(h) = O(h) + T(h-1) where h is the height of the tree. Therefore time complexity is O(h^2) and since h= log N in case of complete binary tree therefore time complexity is logN *logN? Am i correct?
Great explanation, Sir!! However, I was surprised to see the trivial dfs based solution not giving TLE upon submission. It may have worked on Leetcode, the dfs solution would definitely not work in an actual interview (we are required to do better). Thanks for explaining the more intuitive approach.
Hello Sir,I have a doubt regarding one problem,I'm not sure if that can be done by DP. The question is similar to minimum cost path sum but instead of going from (0,0) to(n,n),we can go from any point of first column to any point of last column ((x,0)->(y,n))!Allowed moves are:up,down,right can u please suggest how can I approach this problem?
why? why? why? why did I not watch this earlier... an amazing explanation as always. Thank you very much!
Welcome :)
Were you got asked this question in an interview ?
Overacting
The man , the myth , the legend uploads once again!
😅
@TechDose There can be more optimization done for space complexity as here we are using recursion so the stack size will be Theta(N)
Here is the sample implementation:
```
class Solution {
// Return tree depth in O(d) time.
public int computeDepth(TreeNode node) {
int d = 0;
while (node.left != null) {
node = node.left;
++d;
}
return d;
}
// Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
// Return True if last level node idx exists.
// Binary search with O(d) complexity.
public boolean exists(int idx, int d, TreeNode node) {
int left = 0, right = (int)Math.pow(2, d) - 1;
int pivot;
for(int i = 0; i < d; ++i) {
pivot = left + (right - left) / 2;
if (idx right).
// Perform binary search to check how many nodes exist.
int left = 1, right = (int)Math.pow(2, d) - 1;
int pivot;
while (left
Yea, we can use loop to avoid space.
what actually happens to pointer after deleteing.
code:-
int main()
{
int a=5;
int *p=&a;
cout
@@sanjeevashoka7948 delete operation is invalid on static memory it only is valid on heap memory
So much of concepts in a single video🙏🏼
Your explanations are very clear. Clean and concise! Thanks.
Loved your explanation. The code is very simple. But you explained the dry run very nicely.
Thanks :)
@@techdose4u int countNodes(TreeNode* root) {
if(!root)
return 0;
int res=0;
if(root->left && root->right)
res++;
res +=countNodes(root->left) + countNodes(root->right);
return res;
}
@@techdose4u can you tell me why this logic is wrong
This video is a Very helpful to understand problem of complete binary tree.. I'm saying thanking you sir most 😊 .. to make a such beautiful explanation
Fantastic Explanation
thanks
I love your explanations.
😊
Very nice explanation sir. God bless you.
Thanks
Thank you, you explain it clearly.💯
So basically what we are doing is
T(h) = O(h) + T(h-1) where h is the height of the tree. Therefore time complexity is O(h^2) and since h= log N in case of complete binary tree therefore time complexity is logN *logN? Am i correct?
Superb. Great work sir
Thanks :)
Great explanation, Sir!!
However, I was surprised to see the trivial dfs based solution not giving TLE upon submission. It may have worked on Leetcode, the dfs solution would definitely not work in an actual interview (we are required to do better).
Thanks for explaining the more intuitive approach.
Welcome :)
what solution would work in interview?
Excellent explanation!
Thanks
Thanks, it was really helpfull explanation!
explanation is amazing.
Thanks 😊
Genius. Very impressive
Can you explain the time complexity for a skew-tree ?
Skewed tree cannot be a complete binary tree hence counting no of nodes of a skewed tree is possible by applying any traversal techinque with O(N) TC.
hi can you please make videos on low level system design. superb explanation..
I am currently teaching system design in my classes. You can join that if you wanna learn full system design
Amazing explanation, thank you for your help!
@ 4:21 u said left level=right level=4 hence perfect bst ..how?? it can be skewed from both ends but still not perfect bst right??
Question is about Complete Binary Tree whose property doesn't allow both sided skewed trees.
Sooo good!!
What writing app do you use for writing? I like the color scheme of this app. Much appreciated if you could share
Wacom pro inkspace sketch io
TECH DOSE could not find it online . Any link will help
amazing explanations !!!!
Nice explaination !!
Thanks
better explanation
this is nice video. I have a clarification. what if tree like this
0
0 0
0 0
our program return 7 but node itself is 5.
my bad q's says its complete binary tree.
Thanks for nice explanation
Can you please explain again how did the time complexity came out like that
Hello Sir,I have a doubt regarding one problem,I'm not sure if that can be done by DP.
The question is similar to minimum cost path sum but instead of going from (0,0) to(n,n),we can go from any point of first column to any point of last column ((x,0)->(y,n))!Allowed moves are:up,down,right
can u please suggest how can I approach this problem?
its basically has a variable starting and ending points...so u can just make loop for every starting element of 0th row and return max
Thanks Sir 👍
Welcome :)
Thank you
thank you!
class Solution {
public int countNodes(TreeNode root) {
if(root==null)
return 0;
int lc=1;
TreeNode lt=root.left;
while(lt!=null)
{
lt=lt.left;
lc++;
}
int rc=1;
TreeNode rt=root.right;
while(rt!=null)
{
rt=rt.right;
rc++;
}
if(lc==rc)
return (int)Math.pow(2,lc)-1;
return 1+countNodes(root.left)+countNodes(root.right);
}
}
Interested to know which software do u use to explain and write on? Is it free?
great explaination
Thanks :)
skipped this question many time.... but after seeing this... i am like....whyyy???
Great
Nice
Thanks
Sir how to calculate total depth and what is total depth
Hi sir, Log N * Log N will be faster than N ? Sorry lol I totally forgot all them math..
Take a large value of N and calculate. You will get it :)
you should be teaching in harvard
that is too much man 😅
what is N in time complexity?
Best
thanks
Technically, It's not depth, it's height . And Max depth = height.
👍🏻
👍