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.
@@asishcodes 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 !!!
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
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.... 😂😂😂😂😂.
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)
Big Thank You to Striver. Leveraging the solution from previous video in this playlist. Below is the alternative approach:- /* Algorithm for the main function, isBalanced(root): - Declare and Initialize leftHeight to the return value of the helper function, getMaxDepth(root.left) - Declare and Initialize rightHeight to the return value of the helper function, getMaxDepth(root.right) - If the absolute difference between the leftHeight and rightHeight is greater than 1, return false. - If the left side of the subtree is NOT balanced OR right side of the subtree is NOT balanced, return false. - Return true. Complexity Analysis: - Time Complexity = O(N) - Space Complexity = O(N) Algorithm for the helper function, getMaxDepth(root): - Base case condition - If root is equal to null, return 0. - Main/Recursive case condition - If the root is not equal to null, then the maxDepth will be `1 + max(maxDepth(left of root), maxDepth(right of root)). Return the maxDepth. */ var isBalanced = function(root) { // Edge case if (root === null) { return true; } let leftHeight = getMaxDepth(root.left); //console.log(leftHeight); let rightHeight = getMaxDepth(root.right); //console.log(rightHeight); let diff = Math.abs(leftHeight - rightHeight); //console.log(diff); if (diff > 1) { return false; } if (!isBalanced(root.left) || !isBalanced(root.right)) { return false; } return true; }; var getMaxDepth = function(root) { // Base case condition if (root === null) { return 0; } // Recursive case condition return 1 + Math.max(getMaxDepth(root.left), getMaxDepth(root.right)); };
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.
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.
This approach is also nice ,but we explicitely need to check for left ==-1 && right==-1 I personally prefer using the INT_MAX instead of -1 to demonstrate unbalanced nodes: MY CODE: long long height(TreeNode * root) { if(root!=NULL) { long long left=1+height(root->left); long long right=1+height(root->right); if(abs(left-right)>1) return INT_MAX; return max(left,right); } return 0; } bool isBalanced(TreeNode* root) { long long ans=height(root); if(ans>=INT_MAX) return false; return true; }
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 .
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
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
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 ;
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 didn't get o n square solution. Once u have checked difference of left and right child for root, why are u repeating it for subtrees. Is it possible that tree is balanced but subtrees are not balanced.
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
Can someone tell me why this code doesn't work? On my local machine it gives the right output but on leetcode it fails. int ans=0; int diff(TreeNode* root){ if(root==NULL){ ans = max(ans,0); return 0; } int left = diff(root->left); int right = diff(root->right); int height = 1 + max(left,right); ans = max(ans, abs(right-left)); return height; } class Solution { public: bool isBalanced(TreeNode* root) { if(root==NULL) return true; int height = diff(root); if(ans>1) return false; return true; } };
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
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..........🙂
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
where will i get the notes of these lectures i checked them on the website but there are various blogs written for the same and i am getting confused. can someone please help me
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
I call this method of solving Recursion Exploitation. We design recursion for different purpose but exploit every recursive call separately to find our answer.
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 :)
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
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; }
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; }
How can we take a skew tree here in naive solution, because for skew tree we can have only two nodes to make it Balanced BT otherwise if more nodes then in the first check of first node, it can't be a balanced BT
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
Thank You Striver❣
By seeing 50% video I got the logic and I made it
Really good explanation and the best part is converting the solution of calculating height to find if the tree is balanced is super..
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?
@@asishcodes 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 !!!
@@asishcodes it'll become when the difference condition(if(abs(rh - lh))) will be executed
he made a correction in the code!
such a simple and easy to understand approach ,amazing
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
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....
😂😂😂😂😂.
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)
Big Thank You to Striver.
Leveraging the solution from previous video in this playlist. Below is the alternative approach:-
/*
Algorithm for the main function, isBalanced(root):
- Declare and Initialize leftHeight to the return value of
the helper function, getMaxDepth(root.left)
- Declare and Initialize rightHeight to the return value of
the helper function, getMaxDepth(root.right)
- If the absolute difference between the leftHeight and rightHeight is greater than 1, return false.
- If the left side of the subtree is NOT balanced OR right side of the subtree is NOT balanced, return false.
- Return true.
Complexity Analysis:
- Time Complexity = O(N)
- Space Complexity = O(N)
Algorithm for the helper function, getMaxDepth(root):
- Base case condition
- If root is equal to null, return 0.
- Main/Recursive case condition
- If the root is not equal to null, then the maxDepth
will be `1 + max(maxDepth(left of root), maxDepth(right of root)). Return the maxDepth.
*/
var isBalanced = function(root) {
// Edge case
if (root === null) {
return true;
}
let leftHeight = getMaxDepth(root.left);
//console.log(leftHeight);
let rightHeight = getMaxDepth(root.right);
//console.log(rightHeight);
let diff = Math.abs(leftHeight - rightHeight);
//console.log(diff);
if (diff > 1) {
return false;
}
if (!isBalanced(root.left) || !isBalanced(root.right)) {
return false;
}
return true;
};
var getMaxDepth = function(root) {
// Base case condition
if (root === null) {
return 0;
}
// Recursive case condition
return 1 + Math.max(getMaxDepth(root.left), getMaxDepth(root.right));
};
Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I struggled to understand the O(N^2) approach, but you made it so simple. Thank You!
Work on recursion more
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.
AMazing intuition, understood completely through dry run
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
Good explanation. Walking through the diagram with the code is particularly useful 👍👍👍
Understood! By the way... the comments section of your videos is quite good👍. Want to say this since a very long time..
What an Explanation MANNN!!!!!!!!!!!!!!! 💫💯
Amazing explanation. You are an inspiration.
Another wonderful explanation + solution! Thank you for demystifying trees!
Thanks Striver for such an amazing explanation . never ever thought this question like this . you completely changed my thought process. 🙌
Completed 16/54 (29% done) !!!
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.
Out of the box solution!🤯
Thankyou so much Striver ,you are the best
This approach is also nice ,but we explicitely need to check for left ==-1 && right==-1
I personally prefer using the INT_MAX instead of -1 to demonstrate unbalanced nodes:
MY CODE:
long long height(TreeNode * root)
{
if(root!=NULL)
{
long long left=1+height(root->left);
long long right=1+height(root->right);
if(abs(left-right)>1)
return INT_MAX;
return max(left,right);
}
return 0;
}
bool isBalanced(TreeNode* root) {
long long ans=height(root);
if(ans>=INT_MAX)
return false;
return true;
}
Thank you So much Striver !
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;
}
};
Tq striver❤for this wonderful playlist
this channel is a hidden gem 💎! thank you
loved it...!!!🤩🤩
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;
}
at 4:47 , why did you multiply the time complexities of left and right? why dont we add them?
Excellent explanation as always 🔥🔥🔥🔥👌👌👌👌
Very nice series to under all types of scenarios what can come across from binary tree.
love your dedication! understood sir!
NICE SUPER EXCELLENT MOTIVATED
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
I understood the code and entire explanation : ) 🔥🔥🔥🔥👌👌👌👌
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
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
at 1:23 , it is abs( height(left) - height(right))
Yaa that's correct, that's the required condition for a balanced 🌲
best explanation so far 💯!!!
bit manipulation playlist pls....thanks for this wonderful video
Understood! Such a smart explanation as always, thank you very much!!
thanxx . i was stuck at this question for last two days ...♥
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
Everything becomes easy when it's striver!
great work, and have lots of sponsor ad so that you can provide great videos.
Thanks Striver!, I learnt a lot from you!
Thank you so much sir!
Thanks alot Striver!!!
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 ;
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;
}
}
Yeahhh❤❤❤
I didn't get o n square solution. Once u have checked difference of left and right child for root, why are u repeating it for subtrees. Is it possible that tree is balanced but subtrees are not balanced.
If a subtree is unbalanced then it will ultimately lead to making the whole tree unbalanced.
Great eexplanation
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
Such an excellent video!
Thanks, Striver Bhai!
thaks a lot for such a great explanation !!
i cant figure out how to write the leftH and rightH functions in the brute force...
Can we instead have a global variable, flag and if at any moment left-right subtree height not
Can someone tell me why this code doesn't work? On my local machine it gives the right output but on leetcode it fails.
int ans=0;
int diff(TreeNode* root){
if(root==NULL){
ans = max(ans,0);
return 0;
}
int left = diff(root->left);
int right = diff(root->right);
int height = 1 + max(left,right);
ans = max(ans, abs(right-left));
return height;
}
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root==NULL) return true;
int height = diff(root);
if(ans>1) return false;
return true;
}
};
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!
But for node 1,recursive call will be made for right subtree and then it will return -1
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..........🙂
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 😂😂😂😂
Liked. Cfbr will watch after some time
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
where will i get the notes of these lectures i checked them on the website but there are various blogs written for the same and i am getting confused. can someone please help me
I think you missed the root->right tree steps.
or put that condition right after lh=check(node->left)
understood sir🙇♂️🙏❤
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.
IDK why but your brute force approach is giving WA for other TCs on Leetcode
loved your optimised approach bhaiya
I call this method of solving Recursion Exploitation. We design recursion for different purpose but exploit every recursive call separately to find our answer.
Bhaiya ek Sara imp algorithm ka bhi video bna dona pls .aapka hi smgh aata hai adat lk gya hai😁
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 :)
why the recursion stopped the moment when the left call of 1 node gave -1 the right call must be executed n for 1 node...
Same doubt
@@thegamegoing4320 we can put a check after calculating lh that if it is -1 then return -1.
Thank You Striver:)))))))))))))))))))))))))))))))
I have a doubt Striver Sir,
[1,2,3,4,5,6,null,8] -- this is balanced based on the formula ((lh - rh)
@10:26 correction: height of the tree is 1when stand at 3
Mazedaar approach
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;
}
}
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
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);
}
your are the best nice work you help us a lot
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;
}
Understood
I have completed tree but gonna watch again 🤘
No one asked
@@fuehrercheem you could have simply ignored this comment but no toxicity is necessary...
@@sourabhchoudhary7289 mentioning and then saying u can ignore this wtf
@@fuehrercheem by that comment I meant that I love his content so gonna watch again
It was not commented because someone asked or not
film hein keya??
Thanks buddy ❣️❣️❣️
Amazing series, keep going!
In the first approach, we keep checking for each and every node if its left subtree and right subtree height
yes
In what case "if(lh==-1) return -1;" this will execute?
instead of using we can use boolean array like you did in diameter
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;
}
How can we take a skew tree here in naive solution, because for skew tree we can have only two nodes to make it Balanced BT otherwise if more nodes then in the first check of first node, it can't be a balanced BT
can anyone help me to understand why we are comparing lh and rh == -1 ?like how can the function will return -1?