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!
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
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
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.
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
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.
@@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?
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
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
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.
@@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
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.
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?
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
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.
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)
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])
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...
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
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.
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:)
"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!
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.
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.
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.
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
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.
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.
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
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.
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.
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.
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
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.
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
@@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.
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
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
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.
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?
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.
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
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
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
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
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?
//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 }
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)
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.
Hi Guys, I dont know why my code is not working, for one test case it is failing. Below is my code. Failing test case : [1,2,2,3,null,null,3,4,null,null,4] The left side and right side height, according to what i drew in paint for this array testcase, (assuming level order), height on right and left is 3, so I get it as balanced, but expected is false. :( /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int height(TreeNode *root) { if (!root) return 0; int lsh = 0, rsh = 0; lsh = height(root->left); rsh = height(root->right); if (lsh > rsh) return lsh+1; else return rsh+1; } int BalanceFactor(TreeNode *root) { if (!root) return 0; int lsh = 0, rsh = 0; lsh = height(root->left); rsh = height(root->right); return lsh - rsh; } bool isBalanced(TreeNode* root) { if (!root) return true; if (BalanceFactor(root) == 1 || BalanceFactor(root) == 0 || BalanceFactor(root) == -1) return true;
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)
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??
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.
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
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.
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?
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
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 🤔
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?
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.
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; } };
![[UNCUT]"ทักษิณ" โชว์ฤทธิ์-ครอบครอง "อุ๊งอิ๊ง" ประเทศไทยมีนายกฯ 1แถม1 I คนดังนั่งเคลียร์ I 23 ส.ค.67](http://i.ytimg.com/vi/Uyl4y59R-Sk/mqdefault.jpg)
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
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!
this is one of those problems where the solution is easy to understand but difficult to come up with yourself. great explanation as always !
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
This should be a Medium, especially because LC Maximum Depth of a Binary Tree is Easy, and this question is harder
The O(N^2) solution is easy. If asked to solve in O(N) it would be medium ig.
🤣🤣🤣🤣🤣🤣
This is definetly not an easy question
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
It is so easy problem.... just go and understand the recursion. And every think will be easy
It's very easy and obvious if you study trees for 20 min
I believe you find it easy now 😂
@@siddhantkumar9492 this made more sense for me
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.
I know right lmao
fr
lmao
tbf, you shouldn't be doing Binary Tree questions without knowing what DFS is.
@@zaakirmuhammad9387 but not knowing the difference between 2 and 0 is okay? lol
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
wow really readable, thank you, you made me understand the algorithme a bit better
Thank you, I did the same method but made an error and was checking the comments if someone has posted this!
Wow, very nicely written. I skipped watching the video after reading this. Thank you for saving some time!
Is this the O(n^2) method?
Same solution, just waaay easier to read than using arrays.
You can also use a nonlocal variable for balanced instead of a class member.
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.
Yeah thats a really good point!
I can't understand the code
///dfs(root.left)///
Is'n root is an list?
@@abuumar8794 Root is not a list. Root is a node (normally an object with properties val, left & right)
@@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?
tks for the one-return trick
I love when you explain something for the first time and it clicks even before seeing the code! Shows how great the explanation is
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
That's exactly what we need to do without making it more complex.
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
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.
@@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
Great video again. Do you think you could do a general video on recursive problem solving like the graph or dynamic programming videos?
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.
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?
you can use a BFS and check if the max depth == ceil(log(N))
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
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.
that's why I did too
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)
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])
I dont know how this problem falls in easy category!!
IKR! this is so wrong!
@@overcharged2078 Lowered my self confidence ngl lol
Thank you so much for this series! Good luck in your future endeavors! 🍀
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...
This explanation is one of the best you have ever made
good job mate!. yoiur videos are such a great help
your channel happens to be my "" THE go to place" for leetcode problems
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
shouldn't it return -1 if the node is None? and 0 if it's a single node?
I was looking for someone else that noticed. His definition of height is incorrect.
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!!!!
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:)
"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!
Does he run the code as is? How would the program know what is .left and .right if it wasn't previously stated?
Couldve used a global variable for result bool instead of passing it along everytime
right?
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.
hey, can you share your code?
@@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
@@UyenTran-hz5mv th-cam.com/video/QfJsau0ItOY/w-d-xo.html&lc=UgxvRQn6588LrWOWxZB4AaABAg
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.
Nice! Why do we take the max from the left and right subtree heights ?
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.
this one is VERY difficult for me
The human brain crashes when looking at recursive functions.
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
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?
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.
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.
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
What is the run time for your algorithm?
Y self.res=True outside function
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.
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.
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.
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
Amazing video as always!
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.
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
why did you consider the height of a node without any child nodes 1 and not 0?
I didn't get this too
@@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.
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
why are we using -1 to signal that the subtrees are unbalanced?
Is there an iterative solution for this?
I don't even get what a balanced tree, let alone its method, so I came here for help LMAO. Thanks for your explanation!
That tree at 1:36 is exactly what I did...😆😆
That moment when you find the solution, come here to see how good you did, and your algorithm was the naive one. Oof.
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
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.
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?
I believe that it will not early terminate, it will still go through all the nodes once and then return False
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.
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
Basically, post order traversal.
Yup, exactly!
You are just the best, thank you so much!
Hey, awesome video yet again. Next, can you please solve the leetcode 218 - The Skyline Problem.
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
the tree isn't guaranteed to be binary search, just binary
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
left and subtrees also have to be balanced. if you run the code on leetcode, it will not be accepted
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
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?
Thank you for the video. It is very easy to understand
why is the height of a single node = 1
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
//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
}
I would use a tuple instead of an list when returning values from dfs
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)
Could someone explain a little bit what does 0 and 1 in "balanced = left[0] and right [0] and abs(left[1] - right[1]
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.
Hi Guys,
I dont know why my code is not working, for one test case it is failing. Below is my code.
Failing test case : [1,2,2,3,null,null,3,4,null,null,4]
The left side and right side height, according to what i drew in paint for this array testcase, (assuming level order), height on right and left is 3, so I get it as balanced, but expected is false.
:(
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int height(TreeNode *root)
{
if (!root)
return 0;
int lsh = 0, rsh = 0;
lsh = height(root->left);
rsh = height(root->right);
if (lsh > rsh)
return lsh+1;
else
return rsh+1;
}
int BalanceFactor(TreeNode *root)
{
if (!root)
return 0;
int lsh = 0, rsh = 0;
lsh = height(root->left);
rsh = height(root->right);
return lsh - rsh;
}
bool isBalanced(TreeNode* root) {
if (!root)
return true;
if (BalanceFactor(root) == 1 || BalanceFactor(root) == 0 || BalanceFactor(root) == -1)
return true;
return false;
}
};
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
I wish this solution is also there for other languages other than Python
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??
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.
amazing explanation, thanks
ik you get this a lot from me, but what can I say except great video.
I was able to solve it O(N^2), but I wondering if O(N) solution is possible. Nice video!
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.
is it possible to solve this problem iteratively?? just curious..
Amazing explanantion!
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
where did we start from the bottom ?? its confusing
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?
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.
You're the best, I swear...
Thanks man, liked
Your voice is kinda similar to the guy behind Daily Dose of Internet.
Hey everyone, this is YOUR daily dose of leetcode 😉
@@NeetCode You should start saying that.. Or something similar..
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?
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
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 🤔
Hi I tried getting the 10% discount, but when I checkout it says coupon not valid. Can you help?
Sorry about that, is the coupon code "neetcode"? Not sure what issue is, maybe it depends on location
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
The most easy problem.. It’s implemente the basic recursion
When/where are the height values set?
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;
}
};
what is left[1] and right [1] ?
I dont see how naive complexity is O(n^2) as in the recursive calls you would only be doing that node and down??
great thank you sir
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?
Great video. But this time the code is confusing.
Thanks!
I did not understand how is the count of the height being kept.
that was really helpful
so based on example 1 what is dfs(root.left) in that example?
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.
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
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;
}
};
Yes, this was the O(n^2) solution mention from 1:58 to 3:59
time complexity will be O(nlogn)