Balanced Binary Tree - Leetcode 110 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: neetcode.io/problems/balanced...
0:00 - Read the problem
1:40 - Drawing Explanation
9:00 - Coding Explanation
leetcode 110
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#binary #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

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

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

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

🤣🤣🤣🤣🤣🤣

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

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

[@raidenmotors3033]

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

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

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

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

[@TharaMesseroux1]

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

[@sudluee]

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

[@ratikchauhan4003]

Amazing video as always!

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

[@aaen9417]

This explanation is one of the best you have ever made

[@cyliu2434]

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

[@enigmatekinc3573]

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

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

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

[@gunjanroy8876]

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

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

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

[@horumy]

You are just the best, thank you so much!

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

[@jugalparulekar661]

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

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

[@elviramadigan3970]

amazing explanation, thanks

[@boomboom-jj9jo]

this is a great explanation

[@rahulbhatia9076]

Amazing explanantion!

[@user-ej3iw8lw3w]

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.

[@user-qc4fv3je2d]

Shut the front dooor!!!!

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

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

[@symbol767]

Thanks man, liked

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

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

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

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

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

[@anwarmohammad5795]

that was really helpful

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

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

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

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

[@andreytamelo1183]

Thanks!

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

[@juhabach6371]

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

[@ameynaik2743]

Basically, post order traversal.

[@NeetCode]

Yup, exactly!

[@divinsmathew]

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

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

[@breakthecode8323]

You're the best, I swear...

[@marcelsantee1809]

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

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

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

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

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

[@sanooosai]

great thank you sir

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

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

[@gustavofreitas3734]

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

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

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

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

[@tynshjt]

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

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

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

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

[@amitozazad1584]

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

[@kunalkheeva]

Best!

[@loopzz5526]

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

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

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

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

[@MafiaXII]

Is there an iterative solution for this?

[@director8656]

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

[@Ebrahem-outlook]

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

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

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

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

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

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

[@user-nj8lu8ld9e]

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

[@mjpaynewales]

When/where are the height values set?

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

[@putin_navsegda6487]

this one is VERY difficult for me

[@mjpaynewales]

The human brain crashes when looking at recursive functions.

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

[@abodier9610]

why is the height of a single node = 1

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

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

[@aayush9080]

time complexity will be O(nlogn)

[@namanvohra8262]

Great video. But this time the code is confusing.

[@RN-jo8zt]

anyone can explain why leaf node height is considering 1 insted of 0 .7:00

[@ahobilesh5323]

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

[@shasankkumar7246]

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

[@entoo9677]

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

[@dimakavetskyy2082]

have you ever worked at a faang?

[@NeetCode]

Yes :)

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

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

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

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

[@vijayparmar7907]

very weird observation : your 'Hey everyone' exactly sounds like the canadian lad's ! are you and the canadian lad the same person 🕵 ?

[@harshitdandelia4663]

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