@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?
The man , the myth , the legend uploads once again!
😅
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
Your explanations are very clear. Clean and concise! Thanks.
@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🙏🏼
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
I love your explanations.
😊
Fantastic Explanation
thanks
Thank you, you explain it clearly.💯
Very nice explanation sir. God bless you.
Thanks
Superb. Great work sir
Thanks :)
Excellent explanation!
Thanks
Thanks, it was really helpfull explanation!
Amazing explanation, thank you for your help!
explanation is amazing.
Thanks 😊
Sooo good!!
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?
Genius. Very impressive
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?
amazing explanations !!!!
Nice explaination !!
Thanks
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
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
Thanks Sir 👍
Welcome :)
what is N in time complexity?
great explaination
Thanks :)
Thanks for nice explanation
Can you please explain again how did the time complexity came out like that
better explanation
@ 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.
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
Interested to know which software do u use to explain and write on? Is it free?
Great
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.
Sir how to calculate total depth and what is total depth
Thank you
thank you!
Nice
Thanks
skipped this question many time.... but after seeing this... i am like....whyyy???
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);
}
}
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 :)
Technically, It's not depth, it's height . And Max depth = height.
👍🏻
👍