L15. Check for Balanced Binary Tree | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@jaydeeppurohit1]

thank's man for the free tutorials very helpful

[@democratcobra]

Incredible mind.

[@SatyamEdits]

Bhaiyaaa...."in Brief" mtlb "in short" hota hai......😅😅

[@AmanAshutoshBCS]

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.???

[@pulkitjain5159]

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.

[@リンゴ酢-b8g]

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.

[@shashwatpriyadarshy7681]

Correction : Instead of && (AND) in the first if-condition of lh & rh, it should be || (OR) .

[@joseph2073]

[@asishcodes]

When will lh or rh becomes -1? And how?

[@100mehulsingh8]

@@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 !!!

[@maheshjindal2622]

@@asishcodes it'll become when the difference condition(if(abs(rh - lh))) will be executed

[@maheshjindal2622]

he made a correction in the code!

[@abhishekarora437]

Never thought that this question can be solved like this also....very easy code A big thank you to striver

[@warriorgaming9509]

So true man

[@tanishqdadhich8589]

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 !

[@parthsalat]

💯💯💯

[@only_for_fun1234r]

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

[@beingSenpai]

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)

[@kennethantonyjohn2708]

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

[@chiragvohra6673]

how lh value will be -1 can u explain ?

[@VV-ps8rt]

@@chiragvohra6673 if at any node in left subtree is not balanced, ultimately will result in unbalanced left subtree

[@tamannasharma3524]

Really good explanation and the best part is converting the solution of calculating height to find if the tree is balanced is super..

[@saicharangarapati2517]

Thank You Striver❣ By seeing 50% video I got the logic and I made it

[@prakharmangal1152]

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

[@VV-ps8rt]

after calculating lh, you can immediately check if its -1 and return, will save lot of time especially if its right leaning tree

[@adamyasharma_0135]

such a simple and easy to understand approach ,amazing

[@SagarSrikant]

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)); };

[@PabitraPadhy]

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.

[@ruchivora1190]

I struggled to understand the O(N^2) approach, but you made it so simple. Thank You!

[@arishsheikh3000]

Work on recursion more

[@ayushkumar-wt2wm]

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; } };

[@yashmundankar24]

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; } };

[@ishangujarathi10]

AMazing intuition, understood completely through dry run

[@utsavseth6573]

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.... 😂😂😂😂😂.

[@stith_pragya]

Thank You So Much for this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@kakadiazeel]

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; } }

[@CuriousAyushi]

What an Explanation MANNN!!!!!!!!!!!!!!! 💫💯

[@akashddeepchitransh4537]

Amazing explanation. You are an inspiration.

[@engineervinay]

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.

[@ritikshandilya7075]

Thankyou so much Striver ,you are the best

[@vasudhajha9115]

Another wonderful explanation + solution! Thank you for demystifying trees!

[@bhavkushwaha]

Thankyou Striver, Understood!

[@viditsrivastava1747]

Out of the box solution!🤯

[@sankalpjain4841]

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.

[@anujaditya02]

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.

[@_nucleus]

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

[@rishabhnegi9806]

@@_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 .

[@prakhar_pratyush]

@@rishabhnegi9806 yes I submitted both the approaches on leetcode. Putting lh==-1 before calling for rh, reduces the runtime by half.

[@CodePinaka]

was looking for the same doubt in the comment section.... thanks vro

[@AmanYadav-jf1yy]

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); }

[@pulkitjain5159]

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

[@udayptp]

Noice

[@subhajitdey135]

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; }

[@muktarsayeed9198]

Good explanation. Walking through the diagram with the code is particularly useful 👍👍👍

[@apmotivationakashparmar722]

Thank you So much Striver !

[@PrashantSingh-qr3vn]

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

[@DrOnZeR2022]

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

[@mysterious5729]

​@@DrOnZeR2022 surprise! Course launched ✨

[@DrOnZeR2022]

@@mysterious5729 🤣🤣 this thing he said 2 year before in a vedio

[@lifehustlers164]

Completed 16/54 (29% done) !!!

[@nagame859]

Understood! By the way... the comments section of your videos is quite good👍. Want to say this since a very long time..

[@uRamPlus]

this channel is a hidden gem 💎! thank you

[@rohandevaki4349]

at 1:23 , it is abs( height(left) - height(right))

[@omkumar4211]

Yaa that's correct, that's the required condition for a balanced 🌲

[@himanshugupta7010]

Thanks Striver for such an amazing explanation . never ever thought this question like this . you completely changed my thought process. 🙌

[@yashpaunikar671]

loved it...!!!🤩🤩

[@deepakjain4481]

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

[@TheWierdVibe]

Everything becomes easy when it's striver!

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@noob_coder4017]

Tq striver❤for this wonderful playlist

[@krishnakanttiwari517]

Thank you so much sir!

[@codeman3828]

Great eexplanation

[@firebout7675]

bit manipulation playlist pls....thanks for this wonderful video

[@itzmartin20]

love your dedication! understood sir!

[@adebisisheriff159]

Thanks alot Striver!!!

[@shameemahamad2617]

Very nice series to under all types of scenarios what can come across from binary tree.

[@ajaykushwaha6137]

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.

[@HimanshuSingh-zu4ht]

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

[@amanbhadani8840]

Just do the dry run once on copy,u will understand better.

[@devanshrai8972]

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; }

[@rohandevaki4349]

at 4:47 , why did you multiply the time complexities of left and right? why dont we add them?

[@nawabkhan4916]

great work, and have lots of sponsor ad so that you can provide great videos.

[@gangsta_coder_12]

Excellent explanation as always 🔥🔥🔥🔥👌👌👌👌

[@annaswaheed2615]

best explanation so far 💯!!!

[@cinime]

Understood! Such a smart explanation as always, thank you very much!!

[@Anand-zg6jv]

thanxx . i was stuck at this question for last two days ...♥

[@subramanir8438]

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

[@deepanshurohilla2114]

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

[@deepanshurohilla2114]

sorry my bad i wrote this comment only based on the pseudo code at 11:15 its fine now 😂😂😂😂

[@shivam4you744]

I understood the code and entire explanation : ) 🔥🔥🔥🔥👌👌👌👌

[@tushar5359]

Thanks Striver!, I learnt a lot from you!

[@niranjanraje7160]

In the first approach, we keep checking for each and every node if its left subtree and right subtree height

[@rajkrishnan9961]

yes

[@akashverma5756]

I call this method of solving Recursion Exploitation. We design recursion for different purpose but exploit every recursive call separately to find our answer.

[@theankurpathak]

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.

[@yashmundankar24]

If a subtree is unbalanced then it will ultimately lead to making the whole tree unbalanced.

[@abhishekverma332]

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!

[@parthapratimghose173]

i submitted by myself something si,miliar to the 2nd i got 99% best 4ms solution some extra recursion you have used ?

[@Usurperhk]

Leetcode's runtime is a scam. Focus on the time complexity of code you write.

[@KrishnaSharma-bv5ys]

Please show the code of 1st approach

[@matrixtoogood5601]

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

[@tanishqdadhich8589]

@@matrixtoogood5601 Sounds like avalid point!

[@Nikita-hv5jm]

thaks a lot for such a great explanation !!

[@KeepCalm__]

@10:26 correction: height of the tree is 1when stand at 3

[@Aditya-wy4ci]

But for node 1,recursive call will be made for right subtree and then it will return -1

[@thatowlfromhogwarts490]

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); }

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

Yeahhh❤❤❤

[@lsdxsaurabh2798]

IN find height function base condition should return -1 . otherwise function will return height + 1 .

[@rhl_]

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 :)

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@stith_pragya]

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..........🙂

[@dakshchandore6435]

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 ;

[@animeshsrivastava9938]

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; } }

[@gigglezone3432]

Can we instead have a global variable, flag and if at any moment left-right subtree height not

[@studyonly9622]

I think you missed the root->right tree steps. or put that condition right after lh=check(node->left)

[@KartikeyTT]

tysm sir

[@sauravchandra10]

Mazedaar approach

[@adityapandey23]

Understood

[@saikirank6357]

In what case either left height or right height is equal to -1?

[@omkumar4211]

Same qn

[@taqimustafa7665]

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

[@eshanchourasia287]

Bhaiya ek Sara imp algorithm ka bhi video bna dona pls .aapka hi smgh aata hai adat lk gya hai😁

[@stark2461]

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

[@tanveer.shaikh]

instead of using we can use boolean array like you did in diameter

[@rahulsbhatt]

Such an excellent video! Thanks, Striver Bhai!

[@subhajitdey135]

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

[@Sakthivel-zq1hb]

I have a doubt Striver Sir, [1,2,3,4,5,6,null,8] -- this is balanced based on the formula ((lh - rh)

[@utkarsh_108]

IDK why but your brute force approach is giving WA for other TCs on Leetcode

[@harshkumargupta8538]

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...

[@thegamegoing4320]

Same doubt

[@harshkumargupta8538]

@@thegamegoing4320 we can put a check after calculating lh that if it is -1 then return -1.

[@nuraynasirzade]

good !

[@codding32world50]

Thank You Striver:)))))))))))))))))))))))))))))))

[@Shivi32590]

thank you

[@depressedguy3566]

it's awesome that you are not uploading all videos in a bulk, in a staggered manner we can complete the course according to your uploads, btw great content

[@manavshah7450]

I disagree with you... He was buzy making the Tree series and didn't upload for a month and now we expected to get the whole series but he is uploading slowly. Placements are going on and it would be beneficial for final year students if he uploads the whole series together.

[@depressedguy3566]

@@manavshah7450 it's okay to disagree and I respect your opinion, but I personally find it more helpful than bulk upload, it's just a personal POV

[@manavshah7450]

@@depressedguy3566 alright. Technically speaking it shouldn't matter to you even if the whole series gets uploaded together. After all you can watch it at your own convenience and pace at youtube.

[@AnkitKumar-jm3cz]

loved your optimised approach bhaiya

[@akashjha7090]

are bhaiya we are checking condition lh==-1 and another one rh==-1 i am confused when lh and rh may be -1

[@codingwithanonymous890]

same dude

[@sourabhchoudhary7289]

I have completed tree but gonna watch again 🤘

[@fuehrercheem]

No one asked

[@sourabhchoudhary7289]

@@fuehrercheem you could have simply ignored this comment but no toxicity is necessary...

[@fuehrercheem]

@@sourabhchoudhary7289 mentioning and then saying u can ignore this wtf

[@sourabhchoudhary7289]

@@fuehrercheem by that comment I meant that I love his content so gonna watch again It was not commented because someone asked or not

[@democratcobra]

film hein keya??

[@surbhiranjan7808]

When does this condition occur? if (rightHeight == -1) return -1; if (leftHeight == -1) return -1;

[@praveenrajs94]

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.

[@lakshsinghania]

@@praveenrajs94 thnks for the explanation! i was looking for the same only

[@piyushverma8207]

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; } };

[@ankitpradhan2499]

i cant figure out how to write the leftH and rightH functions in the brute force...

[@ayushmishra1207]

Bhaiya In which case the height of left or right side will -1 ??

[@pranavmendiratta3166]

Amazing series, keep going!

[@rishabhkesarwani5761]

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; } }