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.

[@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)

[@tamannasharma3524]

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

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

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

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

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

[@adamyasharma_0135]

such a simple and easy to understand approach ,amazing

[@saicharangarapati2517]

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

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

[@shashwatpriyadarshy7681]

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

[@joseph2073]

[@nopecharon]

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

[@100mehulsingh8]

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

[@maheshjindal2622]

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

[@maheshjindal2622]

he made a correction in the code!

[@akashddeepchitransh4537]

Amazing explanation. You are an inspiration.

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

[@lifehustlers164]

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

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

[@bhavkushwaha]

Thankyou Striver, Understood!

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

[@ishangujarathi10]

AMazing intuition, understood completely through dry run

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

[@stith_pragya]

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

[@rohandevaki4349]

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

[@omkumar4211]

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

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

[@TheWierdVibe]

Everything becomes easy when it's striver!

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

[@viditsrivastava1747]

Out of the box solution!🤯

[@firebout7675]

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

[@CuriousAyushi]

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

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@apmotivationakashparmar722]

Thank you So much Striver !

[@uRamPlus]

this channel is a hidden gem 💎! thank you

[@vasudhajha9115]

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

[@noob_coder4017]

Tq striver❤for this wonderful playlist

[@codeman3828]

Great eexplanation

[@nagame859]

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

[@nawabkhan4916]

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

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

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

[@muktarsayeed9198]

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

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

[@Aditya-wy4ci]

But for node 1,recursive call will be made for right subtree and then it will 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; } }

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

[@studyonly9622]

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

[@itzmartin20]

love your dedication! understood sir!

[@utkarsh_108]

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

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

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

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

[@tiger7858]

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

[@adebisisheriff159]

Thanks alot Striver!!!

[@tanveer.shaikh]

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

[@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 ;

[@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)

[@shameemahamad2617]

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

[@himanshugupta7010]

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

[@annaswaheed2615]

best explanation so far 💯!!!

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

[@yashpaunikar671]

loved it...!!!🤩🤩

[@mriduljain1981]

completed lecture 15 of Tree playlist.

[@tushar5359]

Thanks Striver!, I learnt a lot from you!

[@Drizilingfacts]

We can also use map here to keep heights of trees

[@gigglezone3432]

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

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

[@adityapandey23]

Understood

[@teeyaojha4365]

no relevel?

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

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@sauravchandra10]

Mazedaar approach

[@rydmerlin]

In this video you used && when you said ‘or’

[@Shivi32590]

thank you

[@Anand-zg6jv]

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

[@ayushmishra1207]

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

[@KeepCalm__]

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

[@RITIKSINGH-re5ne]

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

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

[@Nikita-hv5jm]

thaks a lot for such a great explanation !!

[@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 😂😂😂😂

[@rohandevaki4349]

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

[@KartikeyTT]

tysm sir

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

Yeahhh❤❤❤

[@abhaykumarsingh3884]

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

[@gangsta_coder_12]

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

[@AnkitKumar-jm3cz]

loved your optimised approach bhaiya

[@cinime]

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

[@shivam4you744]

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

[@rahulsbhatt]

Such an excellent video! Thanks, Striver Bhai!

[@niranjanraje7160]

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

[@rajkrishnan9961]

yes

[@subee128]

Thanks

[@utkarshsingh5960]

why are we checking leftroot =-1?

[@codding32world50]

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

[@nuraynasirzade]

good !

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

[@smartswaggy6114]

why left==-1 o right==-1 condition?

[@eshanchourasia287]

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

[@culeforever5408]

understood

[@ieltsbaba8400]

In what case "if(lh==-1) return -1;" this will execute?

[@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??