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
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
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
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?
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
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.
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
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])
Slightly easier to understand solution- class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: if not root: return True def helper(node): if not node: return 0 left = helper(node.left) right = helper(node.right) if left == -1 or right == -1 or abs(right-left) > 1: return -1 return 1 + max(left, right) return True if helper(root) != -1 else False
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.
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.
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 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?
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
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.
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
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 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
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.
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
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.
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
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.
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 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
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.
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)
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.
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
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
//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 }
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.
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.
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.
@@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.
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
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.
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)
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?
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; } };
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.
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?
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
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.
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
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 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; } };
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??
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;
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 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
🚀 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.
🤣🤣🤣🤣🤣🤣
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.
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
I love when you explain something for the first time and it clicks even before seeing the code! Shows how great the explanation is
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
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
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
you can use a BFS and check if the max depth == ceil(log(N))
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
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])
Slightly easier to understand solution-
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def helper(node):
if not node:
return 0
left = helper(node.left)
right = helper(node.right)
if left == -1 or right == -1 or abs(right-left) > 1:
return -1
return 1 + max(left, right)
return True if helper(root) != -1 else False
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
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.
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 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?
Great video again. Do you think you could do a general video on recursive problem solving like the graph or dynamic programming videos?
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
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 ua-cam.com/video/QfJsau0ItOY/v-deo.html&lc=UgxvRQn6588LrWOWxZB4AaABAg
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
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 dont know how this problem falls in easy category!!
IKR! this is so wrong!
@@overcharged2078 Lowered my self confidence ngl lol
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
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.
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
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!!!!
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
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.
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 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?
good job mate!. yoiur videos are such a great help
your channel happens to be my "" THE go to place" for leetcode problems
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.
Thank you so much for this series! Good luck in your future endeavors! 🍀
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
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.
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
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
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
the tree isn't guaranteed to be binary search, just binary
I would use a tuple instead of an list when returning values from dfs
//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
}
Couldve used a global variable for result bool instead of passing it along everytime
right?
This explanation is one of the best you have ever made
Basically, post order traversal.
Yup, exactly!
That tree at 1:36 is exactly what I did...😆😆
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.
I wish this solution is also there for other languages other than Python
You are just the best, thank you so much!
I was able to solve it O(N^2), but I wondering if O(N) solution is possible. Nice video!
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.
I don't even get what a balanced tree, let alone its method, so I came here for help LMAO. Thanks for your explanation!
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.
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.
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
Does he run the code as is? How would the program know what is .left and .right if it wasn't previously stated?
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 one is VERY difficult for me
The human brain crashes when looking at recursive functions.
You're the best, I swear...
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
Amazing explanantion!
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.
Thank you for the video. It is very easy to understand
Amazing video as always!
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)
amazing explanation, thanks
great thank you sir
Hey, awesome video yet again. Next, can you please solve the leetcode 218 - The Skyline Problem.
The most easy problem.. It’s implemente the basic recursion
time complexity will be O(nlogn)
why is the height of a single node = 1
Thanks man, liked
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;
}
};
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
ik you get this a lot from me, but what can I say except great video.
Thanks!
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;
}
};
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.
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 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.
that was really helpful
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?
Could someone explain a little bit what does 0 and 1 in "balanced = left[0] and right [0] and abs(left[1] - right[1]
CPP -
pair dfs(TreeNode* root) {
pair p;
p.first = 0;
p.second = false;
if (root == nullptr) {
p.first = 0;
p.second = true;
return p;
}
pair left = dfs(root -> left);
pair right = dfs(root -> right);
if (left.second and right.second and abs(left.first - right.first)
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
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.
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
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
Is there an iterative solution for this?
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
That moment when you find the solution, come here to see how good you did, and your algorithm was the naive one. Oof.
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.
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;
}
};
I dont see how naive complexity is O(n^2) as in the recursive calls you would only be doing that node and down??
When/where are the height values set?
where did we start from the bottom ?? its confusing
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 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