i think on 9:21 , it should be if( lh ==-1 || rh == -1) return -1 , beacuse if any of the subtree is unbalanced , my whole tree is unbalanced. if does'nt require to have my both subtree unbalanced.
A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.
Thanks a lot for the explanation, it was very helpful. One further optimization that could be done is to check if lh and rh values right after each recursive call lh = check(node -> left) if lh == -1: return -1 rh = check(node -> right) if rh == -1: return -1 In this case we are not computing the right sub-tree if at all, at any point the left tree breaks the condition
The time complexity of the first approach will be, N Log N, because if the tree is imbalanced, it'll have an early termination. If the tree is skewed it would return False very fast, so worst case is actually when the tree is balanced !
what if the N = 10^8 and node left contains 10^8 -1 nodes and another one node at right side then we go through all the nodes on left side at last termination we come to know that its right after the root node is imblanced then it would taken almost O(N)
If you follow the mycodeschool approach, where height of a null node is -1, then replace the exit condition from return 0 to return -1. also, replace all the -1 in the code to some flag value say, -2 or something in the negative side other than -1. you could also declare that flag as a static const inside the function. If this is done, then if it's balanced, you'll get directly the height of the node passed initially. Assuming, you're following height of a node, is the # of edges from from leaf to that node, in that branch.
@@nopecharon Suppose, when we are calculating the max height of a subtree, it might not satisfy the balanced tree condition, so a height of -1 will be returned instead of the max height !!!
Using Ninja technique 😍😅😅 take an extra variable ans, initially set ans=true and pass this variable to the btHeight(fxn to calculate height of binary tree) function by reference. If in function btHeight, abs(lh-rh)>1 is true then set ans=false. bool isBalanced(TreeNode* root) { if(root==nullptr) return true; bool ans=true; btHeight(root,ans); return ans; } int btHeight(TreeNode* root, bool &ans) { if(root==nullptr) return 0; int lh=btHeight(root->left, ans); int rh=(root->right, ans); if(abs(lh-rh)>1) ans=false; return 1+max(lh,rh); }
yup , i did it too , but your code is still doing extra calculations ,just do a return when left or right has a false and at end you will find that your logic and striver's logic are same
class Solution { boolean isBal=true; public boolean isBalanced(TreeNode root) { helper(root); return isBal; } public int helper(TreeNode root){ if(root==null) return 0; int left = helper(root.left); int right = helper(root.right); int gap = Math.abs(left-right); if(gap>1) isBal=false; int height = Math.max(left,right)+1; return height; } }
i decided to solve this problem on my own first and after solving thought that i should see the optimized approach and when i started watching i realized my solution is exactly same as striver's this was my solution: int getheight(TreeNode* root){ if(root==NULL)return 0; int lh=getheight(root->left); int rh=getheight(root->right); if(lh==-1||rh==-1)return -1; if(abs(lh-rh)>1)return -1; return 1+max(lh,rh); } bool isBalanced(TreeNode* root) { if(getheight(root)==-1)return false; return true; } i don't know how i got this solution and first time so surprised that i got exact same solution as him i saw the previous problems solution so i knew we just have to make changes in that code.
Me solving a question on my own by some magic once in a bluemoon. Le striver: So the naive approach is.....turns out to be my approach..... I am like ...damn, this guy.... 😂😂😂😂😂.
I have a doubt why a person of your caliber is working for some MNC when he can easily build some million dollar business since you are the person who can get things done
Striver does not want to sell paid courser he wants to help students in this way and I think striver loves his profession that's why he is not building his bussines
We can use the brute force code with memoization also : unordered_map st; int height(TreeNode* node) { if (!node) return 0; if(st.find(node)!=st.end()) return st[node]; int l = height(node->left); int r = height(node->right); return st[node]=1 + max(l, r); } bool isBalanced(TreeNode* root) { if (!root) return true; int l=height(root->left); int r=height(root->right); if (abs(l - r) > 1) return false; bool check1 = isBalanced(root->left); bool check2 = isBalanced(root->right); if (!check1 || !check2) return false; return true; }
It should also find the right height of node 1 right? We need to visit the right subtree of node 1 also right? At 11.46 we returned -1 directly after we got lh==-1 before we got the rh.
As said by striver, even if we encounter -1 on the left side we are gonna return -1 as we are explicitly specifying that if left return -1 then the whole function return -1.
Yes I am also confused for the same, if(lh == -1 || rh == -1) return -1; This above statement can only run after, rh = check(node->right); And since in function call we will pass the root, how rh = check(node->right); this can be skipped, it will check for right child of root but both the codes on 12:00 is right because there he is checking before making call to right
@@_nucleus yeah u are right ... even if we have lh as -1, the recursion will still chk for right tree as before calling for root->right we aren't checking whether we got any -1 till this point ... so in my opinion we can just chk if( lh==-1 ) before calling for rh .
I call this method of solving Recursion Exploitation. We design recursion for different purpose but exploit every recursive call separately to find our answer.
Ye dekh k bohot acha lgta h jb you come on to some video of a pro coder to check for a better solution than yours and you find it exactly the same..........🙂
There exist variety of definiton of height and depth of a tree. Some count nodes while some count egdes depends on the problemsetter. In this case it was mentioned in the question what height here is meant. good day :)
just happen in the same video example brother lh become -1 after if(abs(lh-rh)>1) return -1 now again when come to the check fuction here lh =-1 and if(lh==-1or rh==-1) return -1 and then we come out of check function with -1
my approach:: int recur(TreeNode* root, int* ans) { if(root==NULL) return 0; int l = recur(root->left,ans); int r = recur(root->right,ans); if(abs(l-r)>1) *ans=0; return max(l,r)+1; } bool isBalanced(TreeNode* root) { int ans = 1; recur(root,&ans); if(ans==0) return false; else return true; }
Check for Balanced Binary Tree Solution in JAVA: public boolean isBalanced(TreeNode root) { return height(root) != -1; } public int height(TreeNode root) { if(root == null ) return 0; int left = height( root.left ); if( left == -1 ) return -1; int right = height( root.right ); if( right == -1 ) return -1; if( Math.abs( left - right ) > 1 ) return -1; return Math.max( left, right ) +1; }
Bhaiya at 11:02 I don't think so that -1 will be returned earlier before visiting the right portion. right recursive calls will be done before returning -1 as answer Please correct em if i am wrong
how can the height be -1 since the height can either be zero or >zero and i didn't understand this line if(leftHieght == -1 ) return -1 and if (rightHeight == -1 ) return -1 ;
Actually, while submitting on Leetcode the latter solution (approach 2) is faster than 64.02% of C++ online submissions although being O(n) whereas the earlier is faster than 90.42% of C++ submission though it being O(n^2). I am actually not getting this, or I am missing anything. Kindly help!
Leetcode test cases might not be of very big trees with billions of nodes. In smaller examples, time complexity will not explain the running/execution time accurately since asymptotic analysis assumes almost infinitely large sizes. For smaller test cases, execution time will depend on network latency, CPU thread switching etc. which is pretty non-deterministic
I solved this in O(N) but using this approach class Solution { class Pair{ boolean condn; int num; Pair(boolean condn,int num){ this.condn=condn; this.num=num; } } public Pair getAns(TreeNode root){ if(root==null){ return new Pair(true,0); } Pair lh=getAns(root.left); Pair rh=getAns(root.right); if(Math.abs(lh.num-rh.num)>1 || !lh.condn || !rh.condn){ return new Pair(false,1+Math.max(lh.num,rh.num)); } return new Pair(true,1+Math.max(lh.num,rh.num)); } public boolean isBalanced(TreeNode root) { return getAns(root).condn; } }
One more Solution using the pair that contains both height and isBalance . T.C. -> O(N) class Solution { class pair{ int height; boolean isbal; pair(int height,boolean isbal){ this.height=height; this.isbal=isbal; } pair(){}; } public boolean isBalanced(TreeNode root) { pair ans = isBalanceHelper(root); return ans.isbal; }
How is the time complexity of the brute force solution O(n*n) and not O(2*n). Dont the recursion calls of the findH finishes first and then for the function check() starts ? I know that this recursion has overlapping sub problems. But why is the time complexity O(n*n) for the overall brute force
10:18 here why is it fine if lh-rh is equal to 1. Still it's an unbalanced tree right. Wondering why greater than 1 is taken instead of greater than or equal to 1
when either of the subtree would be unbalanced,the previous function call would have returned -1 to them,so if unbalancing is found,we dont need to check further
the line lh = check(root->left) means that check whether the left subtree is balanced or not, and if that function returns -1 (which is stored in the lh variable), it means that the left subtree is not balanced. same is the condition with right subtree, if either of them turn out to be unbalanced then the entire tree is unbalanced.
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
thank's man for the free tutorials very helpful
Incredible mind.
Bhaiyaaa...."in Brief" mtlb "in short" hota hai......😅😅
Sir, Timestamp 8 minute and 10 second. Sir, I am unable to understand in what case we will be getting -1 for lh and rh.???
i think on 9:21 , it should be if( lh ==-1 || rh == -1) return -1 , beacuse if any of the subtree is unbalanced , my whole tree is unbalanced. if does'nt require to have my both subtree unbalanced.
A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.
Never thought that this question can be solved like this also....very easy code
A big thank you to striver
So true man
Thanks a lot for the explanation, it was very helpful.
One further optimization that could be done is to check if lh and rh values right after each recursive call
lh = check(node -> left)
if lh == -1:
return -1
rh = check(node -> right)
if rh == -1:
return -1
In this case we are not computing the right sub-tree if at all, at any point the left tree breaks the condition
how lh value will be -1 can u explain ?
@@chiragvohra6673 if at any node in left subtree is not balanced, ultimately will result in unbalanced left subtree
The time complexity of the first approach will be, N Log N, because if the tree is imbalanced, it'll have an early termination.
If the tree is skewed it would return False very fast, so worst case is actually when the tree is balanced !
💯💯💯
I didn't understand why very fast , its has to travel the complete height of left skew which will be (N) because we are traversing from root
what if the N = 10^8 and node left contains 10^8 -1 nodes and another one node at right side then we go through all the nodes on left side at last termination we come to know that its right after the root node is imblanced then it would taken almost O(N)
If you follow the mycodeschool approach, where height of a null node is -1, then replace the exit condition from return 0 to return -1.
also, replace all the -1 in the code to some flag value say, -2 or something in the negative side other than -1.
you could also declare that flag as a static const inside the function.
If this is done, then if it's balanced, you'll get directly the height of the node passed initially.
Assuming, you're following height of a node, is the # of edges from from leaf to that node, in that branch.
Correction : Instead of && (AND) in the first if-condition of lh & rh, it should be || (OR) .
When will lh or rh becomes -1? And how?
@@nopecharon Suppose, when we are calculating the max height of a subtree, it might not satisfy the balanced tree condition, so a height of -1 will be returned instead of the max height !!!
@@nopecharon it'll become when the difference condition(if(abs(rh - lh))) will be executed
he made a correction in the code!
Thank You Striver❣
By seeing 50% video I got the logic and I made it
I struggled to understand the O(N^2) approach, but you made it so simple. Thank You!
Work on recursion more
Python Solution:
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def check(node):
if node == None:
return 0
lh = check(node.left)
rh = check(node.right)
if lh == -1 or rh == -1 or abs(lh-rh) > 1:
return -1
return 1 + max(lh, rh)
return check(root) != -1
after calculating lh, you can immediately check if its -1 and return, will save lot of time especially if its right leaning tree
such a simple and easy to understand approach ,amazing
Really good explanation and the best part is converting the solution of calculating height to find if the tree is balanced is super..
class Solution {
public:
bool res=true;
int height_of_tree(TreeNode *root)
{
if(root==NULL)
{
return 0;
}
int left=height_of_tree(root->left);
int right=height_of_tree(root->right);
if(abs(left-right)>1)
res=false;
return max(left,right)+1;
}
bool isBalanced(TreeNode* root) {
height_of_tree(root);
return res;
}
};
Did the same thing.
class Solution {
public:
int func(TreeNode* root,bool &b){
if(root==NULL){
return 0;
}
int lh=func(root->left,b);
int rh=func(root->right,b);
if(abs(lh-rh)>1) b=false;
return 1+max(rh,lh);
}
bool isBalanced(TreeNode* root) {
if(root==NULL) return true;
bool b=true;
func(root,b);
return b;
}
};
Completed 16/54 (29% done) !!!
Using Ninja technique 😍😅😅
take an extra variable ans, initially set ans=true and pass this variable to the btHeight(fxn to calculate height of binary tree) function by reference.
If in function btHeight, abs(lh-rh)>1 is true then set ans=false.
bool isBalanced(TreeNode* root) {
if(root==nullptr)
return true;
bool ans=true;
btHeight(root,ans);
return ans;
}
int btHeight(TreeNode* root, bool &ans)
{
if(root==nullptr)
return 0;
int lh=btHeight(root->left, ans);
int rh=(root->right, ans);
if(abs(lh-rh)>1)
ans=false;
return 1+max(lh,rh);
}
yup , i did it too , but your code is still doing extra calculations ,just do a return when left or right has a false and at end you will find that your logic and striver's logic are same
Noice
AMazing intuition, understood completely through dry run
class Solution {
boolean isBal=true;
public boolean isBalanced(TreeNode root) {
helper(root);
return isBal;
}
public int helper(TreeNode root){
if(root==null)
return 0;
int left = helper(root.left);
int right = helper(root.right);
int gap = Math.abs(left-right);
if(gap>1)
isBal=false;
int height = Math.max(left,right)+1;
return height;
}
}
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thankyou Striver, Understood!
i decided to solve this problem on my own first and after solving thought that i should see the optimized approach and when i started watching i realized my solution is exactly same as striver's
this was my solution:
int getheight(TreeNode* root){
if(root==NULL)return 0;
int lh=getheight(root->left);
int rh=getheight(root->right);
if(lh==-1||rh==-1)return -1;
if(abs(lh-rh)>1)return -1;
return 1+max(lh,rh);
}
bool isBalanced(TreeNode* root) {
if(getheight(root)==-1)return false;
return true;
}
i don't know how i got this solution and first time so surprised that i got exact same solution as him i saw the previous problems solution so i knew we just have to make changes in that code.
Understood! By the way... the comments section of your videos is quite good👍. Want to say this since a very long time..
Me solving a question on my own by some magic once in a bluemoon.
Le striver: So the naive approach is.....turns out to be my approach.....
I am like ...damn, this guy....
😂😂😂😂😂.
Thankyou so much Striver ,you are the best
I have a doubt why a person of your caliber is working for some MNC when he can easily build some million dollar business since you are the person who can get things done
Striver does not want to sell paid courser he wants to help students in this way and I think striver loves his profession that's why he is not building his bussines
@@DrOnZeR2022 surprise!
Course launched ✨
@@mysterious5729 🤣🤣 this thing he said 2 year before in a vedio
We can use the brute force code with memoization also :
unordered_map st;
int height(TreeNode* node) {
if (!node)
return 0;
if(st.find(node)!=st.end()) return st[node];
int l = height(node->left);
int r = height(node->right);
return st[node]=1 + max(l, r);
}
bool isBalanced(TreeNode* root) {
if (!root)
return true;
int l=height(root->left);
int r=height(root->right);
if (abs(l - r) > 1)
return false;
bool check1 = isBalanced(root->left);
bool check2 = isBalanced(root->right);
if (!check1 || !check2)
return false;
return true;
}
Everything becomes easy when it's striver!
It should also find the right height of node 1 right?
We need to visit the right subtree of node 1 also right?
At 11.46 we returned -1 directly after we got lh==-1 before we got the rh.
As said by striver, even if we encounter -1 on the left side we are gonna return -1 as we are explicitly specifying that if left return -1 then the whole function return -1.
Yes I am also confused for the same,
if(lh == -1 || rh == -1) return -1;
This above statement can only run after,
rh = check(node->right);
And since in function call we will pass the root, how rh = check(node->right); this can be skipped, it will check for right child of root but both the codes on 12:00 is right because there he is checking before making call to right
@@_nucleus yeah u are right ... even if we have lh as -1, the recursion will still chk for right tree as before calling for root->right we aren't checking whether we got any -1 till this point ...
so in my opinion we can just chk if( lh==-1 ) before calling for rh .
@@rishabhnegi9806 yes I submitted both the approaches on leetcode. Putting lh==-1 before calling for rh, reduces the runtime by half.
was looking for the same doubt in the comment section.... thanks vro
What an Explanation MANNN!!!!!!!!!!!!!!! 💫💯
Thank you So much Striver !
Good explanation. Walking through the diagram with the code is particularly useful 👍👍👍
Another wonderful explanation + solution! Thank you for demystifying trees!
Out of the box solution!🤯
great work, and have lots of sponsor ad so that you can provide great videos.
bit manipulation playlist pls....thanks for this wonderful video
Tq striver❤for this wonderful playlist
at 1:23 , it is abs( height(left) - height(right))
Yaa that's correct, that's the required condition for a balanced 🌲
this channel is a hidden gem 💎! thank you
NICE SUPER EXCELLENT MOTIVATED
I call this method of solving Recursion Exploitation. We design recursion for different purpose but exploit every recursive call separately to find our answer.
I think you missed the root->right tree steps.
or put that condition right after lh=check(node->left)
love your dedication! understood sir!
IDK why but your brute force approach is giving WA for other TCs on Leetcode
Very nice series to under all types of scenarios what can come across from binary tree.
Ye dekh k bohot acha lgta h jb you come on to some video of a pro coder to check for a better solution than yours and you find it exactly the same..........🙂
Great eexplanation
I have a doubt Striver Sir,
[1,2,3,4,5,6,null,8] -- this is balanced based on the formula ((lh - rh)
But for node 1,recursive call will be made for right subtree and then it will return -1
Thanks Striver for such an amazing explanation . never ever thought this question like this . you completely changed my thought process. 🙌
maybe someday i will be called as a genius despite of my horrible failures i will try i will keep going someday i will compete with my dream
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
int height (TreeNode root) {
if (root == null) return 0;
int leftH = height(root.left), rightH = height(root.right);
if ((rightH == -1) || ((leftH == -1)) || (Math.abs(leftH - rightH) > 1)) return -1;
else return Math.max(leftH, rightH) + 1;
}
}
Thanks alot Striver!!!
IN find height function base condition should return -1 .
otherwise function will return height + 1 .
There exist variety of definiton of height and depth of a tree.
Some count nodes while some count egdes depends on the problemsetter.
In this case it was mentioned in the question what height here is meant.
good day :)
Hey Buddy, thanks for such an awesome Video, but can u give an example of when the case will be lh==-1 or rh==-1? I couldn't understand.
just happen in the same video example brother
lh become -1 after if(abs(lh-rh)>1) return -1 now again when come to the check fuction here lh =-1 and if(lh==-1or rh==-1) return -1 and then we come out of check function with -1
Just do the dry run once on copy,u will understand better.
tysm sir
int is_balanced(Node root) {
if(root == NULL) return 0;
int lh = is_balanced(root->l);
if(lh == -1) return -1;
int rh = is_balanced(root->r);
if(rh == -1) return -1;
if(abs(lh-rh)>1) return -1;
return 1+max(lh, rh);
}
Understood
Mazedaar approach
loved it...!!!🤩🤩
my approach::
int recur(TreeNode* root, int* ans)
{
if(root==NULL) return 0;
int l = recur(root->left,ans);
int r = recur(root->right,ans);
if(abs(l-r)>1) *ans=0;
return max(l,r)+1;
}
bool isBalanced(TreeNode* root)
{
int ans = 1;
recur(root,&ans);
if(ans==0)
return false;
else return true;
}
Check for Balanced Binary Tree Solution in JAVA:
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
public int height(TreeNode root) {
if(root == null ) return 0;
int left = height( root.left );
if( left == -1 ) return -1;
int right = height( root.right );
if( right == -1 ) return -1;
if( Math.abs( left - right ) > 1 ) return -1;
return Math.max( left, right ) +1;
}
instead of using we can use boolean array like you did in diameter
thank you
Bhaiya at 11:02 I don't think so that -1 will be returned earlier before visiting the right portion.
right recursive calls will be done before returning -1 as answer
Please correct em if i am wrong
sorry my bad i wrote this comment only based on the pseudo code
at 11:15 its fine now 😂😂😂😂
Thanks Striver!, I learnt a lot from you!
how can the height be -1 since the height can either be zero or >zero and i didn't understand this line
if(leftHieght == -1 ) return -1 and if (rightHeight == -1 ) return -1 ;
Bhaiya ek Sara imp algorithm ka bhi video bna dona pls .aapka hi smgh aata hai adat lk gya hai😁
completed lecture 15 of Tree playlist.
best explanation so far 💯!!!
In the first approach, we keep checking for each and every node if its left subtree and right subtree height
yes
thanxx . i was stuck at this question for last two days ...♥
Thanks
We can also use map here to keep heights of trees
function isBalanced (root) {
return height(root) ;
function height(node){
if (!node) return true
let left = height(node.left), right = height(node.right);
return ( !left || !right || Math.abs(left - right) > 1 ) ? false : 1 + Math.max(left, right);
}
};
Can we instead have a global variable, flag and if at any moment left-right subtree height not
Bhaiya In which case the height of left or right side will -1 ??
Understood! Such a smart explanation as always, thank you very much!!
Actually, while submitting on Leetcode the latter solution (approach 2) is faster than 64.02% of C++ online submissions although being O(n) whereas the earlier is faster than 90.42% of C++ submission though it being O(n^2). I am actually not getting this, or I am missing anything. Kindly help!
i submitted by myself something si,miliar to the 2nd i got 99% best 4ms solution some extra recursion you have used ?
Leetcode's runtime is a scam. Focus on the time complexity of code you write.
Please show the code of 1st approach
Leetcode test cases might not be of very big trees with billions of nodes. In smaller examples, time complexity will not explain the running/execution time accurately since asymptotic analysis assumes almost infinitely large sizes.
For smaller test cases, execution time will depend on network latency, CPU thread switching etc. which is pretty non-deterministic
@@matrixtoogood5601 Sounds like avalid point!
Excellent explanation as always 🔥🔥🔥🔥👌👌👌👌
Thank You Striver:)))))))))))))))))))))))))))))))
understood
I understood the code and entire explanation : ) 🔥🔥🔥🔥👌👌👌👌
loved your optimised approach bhaiya
Yeahhh❤❤❤
thaks a lot for such a great explanation !!
good !
@10:26 correction: height of the tree is 1when stand at 3
Liked. Cfbr will watch after some time
In this video you used && when you said ‘or’
I solved this in O(N) but using this approach
class Solution {
class Pair{
boolean condn;
int num;
Pair(boolean condn,int num){
this.condn=condn;
this.num=num;
}
}
public Pair getAns(TreeNode root){
if(root==null){
return new Pair(true,0);
}
Pair lh=getAns(root.left);
Pair rh=getAns(root.right);
if(Math.abs(lh.num-rh.num)>1 || !lh.condn || !rh.condn){
return new Pair(false,1+Math.max(lh.num,rh.num));
}
return new Pair(true,1+Math.max(lh.num,rh.num));
}
public boolean isBalanced(TreeNode root) {
return getAns(root).condn;
}
}
One more Solution using the pair that contains both height and isBalance . T.C. -> O(N)
class Solution {
class pair{
int height;
boolean isbal;
pair(int height,boolean isbal){
this.height=height;
this.isbal=isbal;
}
pair(){};
}
public boolean isBalanced(TreeNode root) {
pair ans = isBalanceHelper(root);
return ans.isbal;
}
public pair isBalanceHelper(TreeNode root){
if(root==null){
pair ans=new pair(0,true);
return ans;
}
pair left=isBalanceHelper(root.left);
pair right=isBalanceHelper(root.right);
pair ans=new pair();
ans.height=1+Math.max(left.height,right.height);
ans.isbal=true;
if(!left.isbal||!right.isbal){
ans.isbal=false;
}
if(Math.abs(left.height-right.height)>1){
ans.isbal=false;
}
return ans;
}
}
How is the time complexity of the brute force solution O(n*n) and not O(2*n). Dont the recursion calls of the findH finishes first and then for the function check() starts ? I know that this recursion has overlapping sub problems. But why is the time complexity O(n*n) for the overall brute force
at 4:47 , why did you multiply the time complexities of left and right? why dont we add them?
10:18 here why is it fine if lh-rh is equal to 1. Still it's an unbalanced tree right. Wondering why greater than 1 is taken instead of greater than or equal to 1
❤
This code won't work when tree is left skewed or right skewed. change return 0 to -1 when root == NULL and change others as -2
In what case either left height or right height is equal to -1?
Same qn
when either of the subtree would be unbalanced,the previous function call would have returned -1 to them,so if unbalancing is found,we dont need to check further
When does this condition occur? if (rightHeight == -1) return -1; if (leftHeight == -1) return -1;
the line lh = check(root->left) means that check whether the left subtree is balanced or not, and if that function returns -1 (which is stored in the lh variable), it means that the left subtree is not balanced. same is the condition with right subtree, if either of them turn out to be unbalanced then the entire tree is unbalanced.
@@praveenrajs94 thnks for the explanation! i was looking for the same only
In the introductory video you told that balanced tree is one whose heigh is at max log(N) , why cant we use that concept here ??
thank you for teaching
Such an excellent video!
Thanks, Striver Bhai!