Balanced Binary Tree - Leetcode 110 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@pranitpawar6136]

This is great! 2 feedback suggestions - please add search by title/LC problem number and make the status column look like checkboxes instead of radio buttons. Thank you very much for all the great helpful content. Makes a BIG difference!

[@benzz22126]

this is one of those problems where the solution is easy to understand but difficult to come up with yourself. great explanation as always !

[@luiggymacias5735]

if you understand how to calculate the height, is easier to come up with the solution, it was more straightfoward because i came across the problem "543. Diameter of Binary Tree" first

[@mnchester]

This should be a Medium, especially because LC Maximum Depth of a Binary Tree is Easy, and this question is harder

[@noober7397]

The O(N^2) solution is easy. If asked to solve in O(N) it would be medium ig.

[@stephanmorel8979]

🤣🤣🤣🤣🤣🤣

[@kthtei]

I think this solution is a bit easier to read. class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: self.balanced = True def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) if (abs(left - right) > 1): self.balanced= False return max(left, right) + 1 dfs(root) return self.balanced

[@atrempest6152]

wow really readable, thank you, you made me understand the algorithme a bit better

[@akshitaven9060]

Thank you, I did the same method but made an error and was checking the comments if someone has posted this!

[@AniruddhaShahapurkar-wu3ed]

Wow, very nicely written. I skipped watching the video after reading this. Thank you for saving some time!

[@antoinenijhuis450]

Is this the O(n^2) method?

[@EngineeringComplained]

Same solution, just waaay easier to read than using arrays. You can also use a nonlocal variable for balanced instead of a class member.

[@amanrai5285]

This is definetly not an easy question

[@siddhantkumar9492]

This is indeed a easy question , it's just that you need to do it in a readable way. def isBalanced(self, root: Optional[TreeNode]) -> bool: balancedtree = True def height(root): nonlocal balancedtree if not root: return 0 left = height(root.left) right = height(root.right) if abs(left-right) >1: balancedtree = False return 0 return 1+max(left, right) height(root) return balancedtree

[@Ebrahem-outlook]

It is so easy problem.... just go and understand the recursion. And every think will be easy

[@WoWUndad]

It's very easy and obvious if you study trees for 20 min

[@MohammedAli-p7e9d]

I believe you find it easy now 😂

[@juliancoward5703]

@@siddhantkumar9492 this made more sense for me

[@gregoryvan9474]

I found it makes it a little easier to write the code if you just use a global variable like in the "Diameter of a Binary Tree" problem you solved. Then you can just update the global variable and not have to return two variables in the dfs function. class Solution(object): def isbalanced(self, root): res = [1] def maxDepth(root): if not root: return 0 left = maxDepth(root.left) right = maxDepth(root.right) if abs(left - right) > 1: res[0] = 0 return 1 + max(left,right) maxDepth(root) return True if res[0] == 1 else False

[@vishalshah6074]

That's exactly what we need to do without making it more complex.

[@jakjun4077]

u can optimizes your solution by adding a condition " if res[0] == 0: return -1" so that u dont have to traverse all the node once a subtree is not balanced and it will eliminate unnecessary steps def isBalanced(self, root): res = [1] def maxDepth(root): if res[0] == 0: return -1 # u can return any number because once we triggered res we have no way back if not root: return 0 left = maxDepth(root.left) right = maxDepth(root.right) if abs(left - right) > 1: res[0] = 0 return 1 + max(left,right) maxDepth(root) return True if res[0] == 1 else False

[@YouProductions1000]

Thanks for this solution. Why do you set res = [1] instead of res = 1. I tried assigning it to an int instead of the array, and for some reason it was not accepted.

[@castorseasworth8423]

@@YouProductions1000 res = [1] makes the outer variable "res" global so you are able to update its value inside the recursive call of the inner dfs function. However, I personally don't like this approach and instead I'd rather use the "nonlocal" keyword to access the the outer variable achieving the very same result in a cleaner fashion: def isBalanced(self, root): res = 1 def maxDepth(root): nonlocal res if res == 0: return -1 # u can return any number because once we triggered res we have no way back if not root: return 0 left = maxDepth(root.left) right = maxDepth(root.right) if abs(left - right) > 1: res = 0 return 1 + max(left,right) maxDepth(root) return True if res == 1 else False

[@faiqito6987]

I love when you explain something for the first time and it clicks even before seeing the code! Shows how great the explanation is

[@suvajitchakrabarty]

Great video. The way I tried it was instead of returning two values, I returned one value: a negative one (-1) if at any node height was not balanced and check that instead. Also, I guess another optimization technique is checking the return value of dfs of the left traversal before doing the dfs for the right. If the left is already not height-balanced just return instead of doing the dfs for the right.

[@NeetCode]

Yeah thats a really good point!

[@abuumar8794]

I can't understand the code ///dfs(root.left)/// Is'n root is an list?

[@suvajitchakrabarty]

@@abuumar8794 Root is not a list. Root is a node (normally an object with properties val, left & right)

[@seanshirazi8638]

@@suvajitchakrabarty Could you please elaborate a bit on your optimization technique? Do you mean first calling dfs(root.left) instead of dfs(root) in the main/isBalnaced method?

[@yitongxie6574]

tks for the one-return trick

[@visakhunnikrishnan7232]

You can use the keyword `nonlocal` to keep track and modify a variable within a function that is within another function. You can use this to keep to track of a variable `balanced`. This way you can check in your base condition whether the node is null or whether `balanced` is `False` and if either are true, return 0.

[@jaimeescobar4551]

that's why I did too

[@mahdi_zaman]

In case returning tuples in recursion is confusing to someone, here's a solution I did where the helper function returns just an integer that is either -1 or the max_depth: ------ def isBalanced(self, root: Optional[TreeNode]) -> bool: def calc_depth(node): if not node: return 0 left = calc_depth(node.left) right = calc_depth(node.right) if abs(left - right) > 1: return -1 if min(left,right) == -1: return -1 return 1 + max(left, right) return calc_depth(root) != -1

[@cyliu2434]

you can use a BFS and check if the max depth == ceil(log(N))

[@xiao5901]

I came up with returning -1 as the return statement once we found the tree is unbalanced, which has several benefits: 1. No Global State: It doesn't rely on class instance variables (self.res or self.balanced), making it more functional and thread-safe. 2. Early Termination: It can stop processing as soon as an unbalanced subtree is found (through the -1 return value), while the other solutions continue processing the entire tree even after finding an unbalanced part. 3. Cleaner Logic: The use of -1 as a sentinel value to indicate an unbalanced subtree in stead of maintaining a separate boolean flag. class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) if abs(left - right) > 1: return -1 return 1 + max(left, right) if left >= 0 and right >= 0 else -1 return dfs(root) >= 0

[@pac1261]

I love the careful explanation of how "2" and "0" differ by more than 1, but the term "recursive DFS" is suddenly introduced as if everyone already knows what it means.

[@christianmorera4127]

I know right lmao

[@yashwanthsai762]

fr

[@brenodonascimentosilva507]

lmao

[@zaakirmuhammad9387]

tbf, you shouldn't be doing Binary Tree questions without knowing what DFS is.

[@flowyriv]

@@zaakirmuhammad9387 but not knowing the difference between 2 and 0 is okay? lol

[@jigglypikapuff]

Thanks for an explanation! I think it may be more efficient if, instead of tracking the additional "balanced" variable, we raise a custom exception if an unbalanced pair of subtrees is found and immediately return False. E.g. def height(root): ... if abs(leftHeight - rightHeight) > 1: raise UnbalancedError ... try: height(root) return True except UnbalancedError: return False

[@Punibaba1]

Great video again. Do you think you could do a general video on recursive problem solving like the graph or dynamic programming videos?

[@prafulparashar9849]

The explanation was on-point as usual. One thing I find that the code is difficult to understand. Check out this python implementation, I tried to unpack what you actually did and this is also working. For me, it is a bit easier to understand. Here you go : class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: # base case if not root: return True # recursion case -- this would also be bottom-up approach # as we are indeed going to the last node and then getting it's height if self.isBalanced(root.left): if self.isBalanced(root.right): lh = self.height(root.left) lr = self.height(root.right) if abs(lh-lr)

[@shawnx7806]

seems good, but I think the code in the video is not that hard to understand if you rewrite the logic like this def isBalanced(self, root: Optional[TreeNode]) -> bool: def dfs(root): if not root: return True, 0 left, right = dfs(root.right), dfs(root.left) #if left and right is balanced (if diff between left and right subtrees are less or equal to 1), return that boolean and the max height of the two if left[0] and right[0] and (abs(left[1] - right[1])

[@dzccccc]

This is what I came up with, I think its a bit more readable and also it checks if an unbalanced node has been found, in which case it would return 0, preventing unnecessary recursion def isBalanced(self, root: Optional[TreeNode]) -> bool: balanced = True if not root: return balanced def dfs(node: Optional[TreeNode]) -> int: nonlocal balanced if not node or not balanced: return 0 left_depth = dfs(node.left) right_depth = dfs(node.right) if abs(right_depth - left_depth) > 1: balanced = False return 1 + max(left_depth, right_depth) dfs(root) return balanced

[@navaneethmkrishnan6374]

Something that helped me: Try to do the naive solution first. It follows the same pattern as diameter of a tree problem. I applied the same recursive idea and got the answer.

[@CJ-ff1xq]

I solved this with the O(n^2) solution of writing a DFS to find the height of a tree and calling that recursively at each level. Calculating both whether it's balanced and the height in a single recursive function just blew my mind...

[@jjdeng9144]

I recursively calculated the height of the tree at every node (with a null node having -1 height.) If the left and right children of a tree have heights differing by more than 1, I raise a custom exception. At the top level, if the custom exception is raised, it returns false. If it successfully complete the height calculation of all node, it returns true.

[@UyenTran-hz5mv]

hey, can you share your code?

[@CharlieWTV2]

@@UyenTran-hz5mv Same idea, without literally raising an exception: class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: self.balanced = True def depth(root): if not root: return 0 else: leftDepth = depth(root.left) rightDepth = depth(root.right) if leftDepth > rightDepth + 1 or rightDepth > leftDepth + 1: self.balanced = False return 1 + max(leftDepth, rightDepth) depth(root) return self.balanced

[@hoainamnguyen6810]

@@UyenTran-hz5mv kzbin.info/www/bejne/h5etpJSrZa6nhbs&lc=UgxvRQn6588LrWOWxZB4AaABAg

[@nw3052]

This code is simple and Pythonic, but I found a big optimisation by checking one subtree first, then if its boolean is false, we immediately return false and 0 as height. Thus we eliminate a lot of cases in which the left subtree is already false and the algorithm would go to the right subtree unnecessarily.

[@Dhanushh]

This right here! Even I was thinking the same. I figured out the solution but couldn't think of anything that will stop us from exploring further if we already found one the subtrees is not balanced. I wonder is this the only way?

[@リンゴ酢-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 no more than 1.

[@Користувачзаблокований]

Shut the front dooor!!!!

[@guths]

This question can be easily solved using golang because you can return two values, bool and int, but in other languages can be hard to find a way to handle with boolean and the height.

[@shilashm5691]

class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: # we are using mutable datastructure, to get the changes from the recurrsion call stacks. res = [0] def dfs(current_node) : # we are looking for last node in every branches of the tree, if it is the last then we returning 1. this 1 is for #making the problem simpler if not current_node : return 1 else : # we just doing dfs. left, right = dfs(current_node.left) , dfs(current_node.right) # for each node, we seeing it left branch and right branch length and we getting the absolute value, if it is > 1, # then from the question we know, it is unbalance, so we are changing the value of the res list if abs(left - right) > 1 : res.pop() res.append(1) return max(left, right) dfs(root) if res[0] == 1 : return False else : return True Code might be longer, but the idea is pretty much straight forward. Go through the code and comments in code

[@sachinfulsunge9977]

I dont know how this problem falls in easy category!!

[@overcharged2078]

IKR! this is so wrong!

[@sachinfulsunge9977]

@@overcharged2078 Lowered my self confidence ngl lol

[@rafaelbnn]

I think with this one and the one about the diameter, one way to solve them is to think how you can use the maxDepth to come up with the solution. I didn't get it by myself on the diameter question, but was able to notice the pattern on this one

[@chair_smesh]

shouldn't it return -1 if the node is None? and 0 if it's a single node?

[@jeffw5902]

I was looking for someone else that noticed. His definition of height is incorrect.

[@LWeRNeO]

There are two problems you need to figure out to solve these kinds of tasks, first is how clever you are to understand/figure out an algorithm, and another one, can you write it in code. I kind of understand what is going on, and in most cases, I figure out a relatively optimal algorithm, the problem is I can't write those algorithms in code. I started python coding 5 months ago, 1 month of which I spent writing a project using one of the frameworks for a python crash course organized by the country's biggest software development company, and another one trying to learn all kinds of theoretical questions to prepare for the interview to get into that company, an interview is about to happen this week. I just hope, that one day I'll be good at solving tasks like this because the guy that was teaching us said that nowadays the world is lacking real software engineers/developers because nowadays the market is creating those who are good with frameworks but not those who know how to solve problems. Good videos BTW:)

[@dinhnhobao]

"I figure out a relatively optimal algorithm, the problem is I can't write those algorithms in code" - I totally relate with you on this! I also had this issue and strangely that no one has mentioned it until you did. What helped me was that I tried to do the problems in categories, so in that sense, I can learn how to implement BFS/DFS via recursion bug-free anytime. For example, you can do 10 tree problems that solve using BFS or DFS. After which, you will have a bug-free BFS/DFS code template that you can reuse anytime you face a new problem. The next time you saw a tree problem and realized that you need to do BFS/DFS, you already have a boilerplate on what things to implement. This would help a lot to implement bug-free solutions. Every person has their personal choice when it comes to implementation. For example, in the dfs function given, instead of checking whether the current node is null, some people would check it one step beforehand and check whether the left child and right child is null. In that sense, the base case would be a leaf node and not a null node. Another personal choice would be what things to return from the recursive call. Returning a pair of (is_tree_balanced, height) is not the only way to do this, there are many possible ways and you can explore!

[@gregwhittier5206]

10:17 left[1] and right[1] won't contain height as stated, but will contain height + 1. It doesn't make a difference when calculating the difference, however. The code in this solution is the same as 104 max depth of a binary tree, which defines depth as the number of nodes in the root to leaf path instead of edges, which isn't the standard definition of depth, which drives me crazy.

[@divinsmathew]

Couldve used a global variable for result bool instead of passing it along everytime right?

[@mohitchaturvedi4556]

This seems easier for me to Understand, Could also be written as: flag = [True] def dfs(root): if not root: return -1 left = dfs(root.left) right = dfs(root.right) if abs(left - right) > 1: flag[0] = False return 1 + max(left, right) dfs(root) return flag[0] Also, In the Diameter problem, you considered height of an empty tree as -1 and that of leaf node as 0, WHEREAS in this video, you considered them 0 and 1 respectively. Which one is better to use in your opinion? Ik both would get the same result in the end.

[@sadia6157]

You could simplify this, do a maxdepth of left and right and if the diff is > 1 its unbalanced. You cannot have unbalanced left or right subtree but a balanced root.

[@abdul.arif2000]

this code is easier to understand # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def isBalanced(self, root: TreeNode) -> bool: def dfs(node): if node is None: return 0 left_height = dfs(node.left) right_height = dfs(node.right) # If the left subtree or the right subtree is not balanced, return -1 if left_height == -1 or right_height == -1: return -1 # If the difference in heights of left and right subtrees is more than 1, return -1 if abs(left_height - right_height) > 1: return -1 # Otherwise, return the height of the current node return max(left_height, right_height) + 1 return dfs(root) != -1

[@OwenWu-f9t]

why are we using -1 to signal that the subtrees are unbalanced?

[@diptindahal909]

Came up with this short python implementation def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ def dfs(root): if not root: return 0 l = dfs(root.left) r = dfs(root.right) if abs(l - r) > 1: self.res = False return 1 + max(l,r) self.res = True dfs(root) return self.res

[@bashaarshah2974]

What is the run time for your algorithm?

[@swaroopkv4540]

Y self.res=True outside function

[@gustavofreitas3734]

Does he run the code as is? How would the program know what is .left and .right if it wasn't previously stated?

[@yejimmy3533]

thought this problem could use the same pattern with probelm "diameter of binary tree" >> directly use global VAR to record 'maxdiff' and finally judge its relation with 1

[@punatar]

My solution (Time: 41 ms (80.55%), Space: 17.7 MB (35.80%) - LeetHub) class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: res = True def dfs(root): nonlocal res if not root: return 0 left = dfs(root.left) right = dfs(root.right) if abs(left - right) > 1: res = False return 1 + max(left, right) dfs(root) return res

[@rabbyhossain6150]

class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: self.isBalanced = True def findMaxHeight(root): if root is None: return 0 left = findMaxHeight(root.left) right = findMaxHeight(root.right) diff = abs(left - right) self.isBalanced = self.isBalanced and diff

[@sykarius01]

class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: res = True def maxDepth(root): nonlocal res if not root: return 0 left = maxDepth(root.left) right = maxDepth(root.right) if abs(left - right) > 1: res = False return 1 + max(left,right) maxDepth(root) return res

[@FUNTasticFlutter]

good job mate!. yoiur videos are such a great help your channel happens to be my "" THE go to place" for leetcode problems

[@Alexkurochkin]

A little bit easier decision that is based on a bool param inside class instead of all these manipulations with arrays in return params. BTW, NeetCode is a GOAT! class Solution: def __init__(self): self.is_balanced = True def isBalanced(self, root: Optional[TreeNode]) -> bool: def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) if abs(left - right) > 1: self.is_balanced = False return 1 + max(left, right) dfs(root) return self.is_balanced if root else True

[@digitulized459]

The easier way is to just check if its an avl tree since avl trees maintain the height balance property, where the left and right subtrees can't differ by more than 1

[@romo119]

the tree isn't guaranteed to be binary search, just binary

[@HIDEHUMAN1]

does line 19 of your codes essentially kick off the recursive process of everything before it and apply them to lower levels of the tree?

[@amitozazad1584]

I was able to solve it O(N^2), but I wondering if O(N) solution is possible. Nice video!

[@marcelsantee1809]

I would use a tuple instead of an list when returning values from dfs

[@TharaMesseroux1]

Thank you so much for this series! Good luck in your future endeavors! 🍀

[@yomamasofat413]

6:39 shouldnt the height of a leaf be 0? Given that height is the number of edges from a node to the deepest leaf. Therefore everything has to be -1 in this video

[@aryankhullar7101]

Can we create an exit condition here so that when we recieve a false the entire recursion tree stops and the final output is false. All options i considered just result in an early return instead of stopping the entire recursion tree.

[@vicenteferrara7626]

Nice! Why do we take the max from the left and right subtree heights ?

[@suvajitchakrabarty]

Because you want to return the height back to the parent node that called it. Height of any node/tree is the max height of its left or right path till the leaf nodes.

[@RushOrbit]

Good explanation! I was able to code a mostly working solution with the explanation alone. Only thing I did different was return -1 if the tree was not balanced.

[@gulfstream1800]

it looks like you have to go through all the nodes to determine if tree is balanced. But in fact, it's enough to find out that one of the subtrees is not balanced to get the answer.

[@lilygranger6264]

why did you consider the height of a node without any child nodes 1 and not 0?

[@ThEHaCkeR1529]

I didn't get this too

[@ijustdey]

​@@ThEHaCkeR1529For example, lets say we have a tree that is just a leaf node (no children). The height of the leaf node is 1. This is cause the node itself account for an height while the two null children have 0 heights. Now imagine this leaf node as a subtree in a bigger tree, its height is 1.​

[@rahuldwivedi4758]

I think this could be simplified. How about this? var findHeight = function(root){ if (root === null) return 1; var leftHeight = 1 + findHeight(root.left); var rightHeight = 1 + findHeight(root.right); return Math.max(leftHeight, rightHeight); } var isBalanced = function(root) { if (root === null) return true; var h1 = findHeight(root.left); var h2 = findHeight(root.right); return Math.abs(h1-h2)

[@tynshjt]

I wish this solution is also there for other languages other than Python

[@luckydb589]

When balanced is False how will the recursion terminate? Or is it just that recursion will not terminate till it reaches root but the balanced value will be False?

[@BoyhoJJ]

I believe that it will not early terminate, it will still go through all the nodes once and then return False

[@okaybossiamonyoutubeakkskd]

//my approach was similar to it (JS) var isBalanced = function(root) { let marker = [1] isUtil(root, marker) return marker[0] === 1 }; let isUtil = function(root, marker){ if(!root) return -1; let l = isUtil(root.left, marker) let r = isUtil(root.right, marker) if(Math.abs(l-r) > 1){ marker[0] = 0 } return l >= r ? l + 1 : r + 1 }

[@aaen9417]

This explanation is one of the best you have ever made

[@ameynaik2743]

Basically, post order traversal.

[@NeetCode]

Yup, exactly!

[@MafiaXII]

Is there an iterative solution for this?

[@abodier9610]

why is the height of a single node = 1

[@neighboroldwang]

Could someone explain a little bit what does 0 and 1 in "balanced = left[0] and right [0] and abs(left[1] - right[1]

[@5464654135756]

I don't even get what a balanced tree, let alone its method, so I came here for help LMAO. Thanks for your explanation!

[@sezermezgil9304]

Great explanation.And i have some doubts in my mind. Does ''balanced'' variable would keep returning False if one of the subtrees are not balanced right ? I can't trace the recursion clearly.

[@yejimmy3533]

yes, because in LINE 14 the return statement is connected by 'and', in this way even one False would continuous return the False statement to the root.

[@blondedadnan7637]

if you're confused by why we need "left[0] and right[0] " in line 14 try the test case [1,2,2,3,null,null,3,4,null,null,4] step by step and it'll make much more sense. If you're not sure how draw the tree from case I just posted google image "array to binary tree". Trust me.

[@juhabach6371]

That tree at 1:36 is exactly what I did...😆😆

[@putin_navsegda6487]

this one is VERY difficult for me

[@mjpaynewales]

The human brain crashes when looking at recursive functions.

[@Ebrahem-outlook]

The most easy problem.. It’s implemente the basic recursion

[@thmstbst]

I dislike how this makes the precision of height hardcoded, but I guess that's leetcode. Does anyone have any tips for not hating these types of narrow solutions? Or Just not hating interview questions in general?

[@b.f.skinner4383]

Thanks for the video. Quick question on line 14: what is the purpose of balance containing booleans for left and right? I omitted it from the code and the output was the same

[@veliea5160]

left and subtrees also have to be balanced. if you run the code on leetcode, it will not be accepted

[@theone.591]

Would the first situation with O(n^2) time complexity be the case where we traverse the tree with dfs and do dfs again for each node to check if the subtree is balanced? Which eventually means nested dfs??

[@user26912]

I think checking everything like that is actually O(N log N) since you "find" every leave node from the top with is N times the depth.

[@staywithmeforever]

I didnt understand why he took True or False False will be at abs(l-r)>1 so when it is not cant u return False when i do that all test cases are not passing nor i understood the values of True or false

[@bigrat5101]

why the line of code, ' if not root: return [True, 0]' , will happen recursively and updating the height of each tree? it only defined under 'if not root' condition...then in line 13, you call dfs by passing left and right..do you mind provide a little more in depth explanations to this? thanks

[@bigrat5101]

ah nvm, i got it. lol 'if not root' is the base node and it will happen when all the nodes have been passed in to dfs, then from each child and up, we get the height of each subtree, and if there is a subtree happens to be False, the recursion will break then return False automatically. otherwise, it will return True. I hope I understood this right?

[@mohamedantar1249]

If just you have created a global variable to store the balance result it would've been much easier: class Solution { public: bool res= true; int dfs(TreeNode* node) { if(!node) return 0; int lefth= dfs(node->left); int righth= dfs(node->right); if(lefth> righth+1 || righth>lefth+1) res= false; return max(lefth,righth)+1; } bool isBalanced(TreeNode* root) { dfs(root); return res; } };

[@bittah-hunter]

What is the space complexity of this? Is it O(h) where h is height of tree? Is h also considered the # of recursive stack calls?

[@shawnfrank5303]

I would say yes. My reasoning is: First h = log n Next, you would always finish the left tree first before going to the right so you will never have the full tree in your call stack at the same time so at most you would have h nodes in your call stack.

[@EE12345]

I prefer the global variable approach to returning two values in one recursive function. Does anyone know if the latter method is better for medium problems?

[@Moch117]

Don't know about mediums but for this problem its much easier to use global variable. Similar approach to the diameter problem Use a function to calculate the height but also take in the global variable as an input. I use Java so i just passed in an array of size 1

[@horumy]

You are just the best, thank you so much!

[@amanshah4196]

where did we start from the bottom ?? its confusing

[@kennethjones8722]

I dont see how naive complexity is O(n^2) as in the recursive calls you would only be doing that node and down??

[@samyakjain8632]

i will give half of my shalary, love from india hope it helps , oh feeling preoud indian armyyyyy jung ke maidaan mai kabhi na haarte

[@aayush9080]

time complexity will be O(nlogn)

[@jugalparulekar661]

Hey, awesome video yet again. Next, can you please solve the leetcode 218 - The Skyline Problem.

[@shasankkumar7246]

is it possible to solve this problem iteratively?? just curious..

[@littlelittlebing]

Why "if not root: return [True, 0 ] "? In leetcode 543, if the root is NULL, it returns negative 1. you explained that the height of a leaf node is 0, so the null node height is -1 🤔

[@namanvohra8262]

Great video. But this time the code is confusing.

[@mjpaynewales]

When/where are the height values set?

[@ErsteSkywalker]

Why not do something like this? (in C++). I can get my head around solutions like this one easier. Basically, there is a helper that returns the height of the tree given a root node. Then, in the isBalanced function, we get the left and right heights using the helper. If the absolute difference between the heights of two children > 1, the node is not balanced. Else, the node is balanced and we recursively call the isBalanced function for the node's left and right children. class Solution { public: bool isBalanced(TreeNode* root) { if (!root) return true; int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); if (abs(leftHeight - rightHeight) > 1) return false; return isBalanced(root->left) && isBalanced(root->right); } int getHeight(TreeNode* root) { if (!root) return 0; return std::max(getHeight(root->left), getHeight(root->right)) + 1; } };

[@hoainamnguyen6810]

Yes, this was the O(n^2) solution mention from 1:58 to 3:59

[@adithyagowda4642]

Your voice is kinda similar to the guy behind Daily Dose of Internet.

[@NeetCode]

Hey everyone, this is YOUR daily dose of leetcode 😉

[@abhishekshah4443]

@@NeetCode You should start saying that.. Or something similar..

[@director8656]

ik you get this a lot from me, but what can I say except great video.

[@entoo9677]

what is left[1] and right [1] ?

[@harshitdandelia4663]

I did not understand how is the count of the height being kept.

[@SOMESHKHANDELIA]

A perhaps more readable solution (better than 82% time complexity and 42% space complexity): class Solution { public: int height_at(TreeNode* root, bool &bal){ if(root == nullptr){ return 0; } else if(root->left == nullptr && root->right == nullptr){ return 0; } else if(root->left != nullptr && root->right == nullptr){ int height_of_left_sub_tree = 1 + height_at(root->left, bal); int height_of_right_sub_tree = 0; int height_diff_at_curr_node = height_of_right_sub_tree - height_of_left_sub_tree; if(height_diff_at_curr_node < -1 || height_diff_at_curr_node > 1){ bal = false; } return height_of_left_sub_tree; } else if(root->left == nullptr && root->right != nullptr){ int height_of_left_sub_tree = 0; int height_of_right_sub_tree = 1 + height_at(root->right, bal); int height_diff_at_curr_node = height_of_right_sub_tree - height_of_left_sub_tree; if(height_diff_at_curr_node < -1 || height_diff_at_curr_node > 1){ bal = false; } return height_of_right_sub_tree; } else{ int height_of_left_sub_tree = 1 + height_at(root->left, bal); int height_of_right_sub_tree = 1 + height_at(root->right, bal); int height_diff_at_curr_node = height_of_right_sub_tree - height_of_left_sub_tree; if(height_diff_at_curr_node < -1 || height_diff_at_curr_node > 1){ bal = false; } return max(height_of_left_sub_tree, height_of_right_sub_tree); } } bool isBalanced(TreeNode* root) { bool bal = true; height_at(root, bal); return bal; } };

[@gunjanroy8876]

Thank you for the video. It is very easy to understand

[@rahuldas6777]

so based on example 1 what is dfs(root.left) in that example?

[@callmeshen9754]

It's a recursion solution so in the first iteration it will be root.left=9 root.right=20 second the root.left will have null in both right and left but the right will have another iteration were root.left=15 and root.right=7 and after that in the third iteration root.left=15 will have null in both left and right and root.right will the same with both left and right null.

[@irishcreature]

Getting an error for this test case: [1,null,2,null,3]

[@UMANG1997]

I also faced the same but then I realized I was missing the closing bracket after right[1] in line 15. Probably same happened with you.

[@lucas0m0james]

I managed to do a little better than this, using the insight that if either subtree is unbalanced, the entire tree must be balanced. So call dfs on say the left node, and check if that's balanced. If it's not we can return without needing to check the right node at all. Doesn't affect time complexity in the worst case, but in the best case the time complexity is the max height of the tree

[@faizamusarrat8705]

Hi I tried getting the 10% discount, but when I checkout it says coupon not valid. Can you help?

[@NeetCode]

Sorry about that, is the coupon code "neetcode"? Not sure what issue is, maybe it depends on location

[@faizamusarrat8705]

Thank you so much, is there a way I can request for few days of free trial? Its a lot of money so I want to try it first, even if it for 3-4 days

[@breakthecode8323]

You're the best, I swear...

[@rahulbhatia9076]

Amazing explanantion!

[@ratikchauhan4003]

Amazing video as always!

[@dimakavetskyy2082]

have you ever worked at a faang?

[@NeetCode]

Yes :)