I cannot thank you enough for your videos . They are crisp and easy to follow. For me , your channel become the one stop for all my learning .Using Python simplified even further.
Right after you explained the problem in the first 3min I understood it immediately and realized I needed to just keep track of the max value in the current path. Looking at your solution, seems I figured it out correctly, thank you man. Liked
Alternative using nonlocal good = 0 def dfs(node, parent): nonlocal good if not node: return if node.val >= parent: good += 1 max_ = max(parent, node.val) dfs(node.left, max_) dfs(node.right, max_) dfs(root, root.val) return good
So simple and easy the way you did it! I was using a Set and adding each good node to my set, but counting good node is so much easier the way you did it. Thanks for the vid as always!
Can be done easily with BFS as well. There is also no rule against updating the node values, so I used BFS and every time I added a new node to the queue I updated that nodes value if it was < root->val
I did the same, but I used extraspace. Used a array to store the path and update count only if the last element of the array is the max element. It pretty much runs the same! class Solution: def goodNodes(self, root: TreeNode) -> int: count = 0 def dfs(root,res): nonlocal count if not root: return res res.append(root.val) if max(res) == res[-1]: count += 1 dfs(root.left,res) dfs(root.right,res) res.pop() return res
i performed a level order traversal and was pushing the node's value if it was greater than max value else i was just pushing the max value for both subtrees(if current node value was greater than max) i just incremented the counter
Nice recursive solution, but this can be more intuitive- kind of similar to LCS prob class Solution { public int goodNodes(TreeNode root) { if (root == null) return 0; return helper(root,root.val); }
public static int helper(TreeNode root, int max){ if (root == null) return 0; if (root.val >= max){ return 1 + helper(root.left,Math.max(root.val,max)) + helper(root.right,Math.max(root.val,max)); } else { return helper(root.left,max) + helper(root.right,max); }
If you add 'res' as a parameter of your dfs function, only one stack frame will be used irrespective of how many times dfs is called recursively because of compiler optimization called "tail recursion"
Done Thanks Similar approach to verifying binary tree, doing a “pre-order- traversal and passing max encountered node from root until now to each recursive call
because in worst case our function can call max number of function calls that are equal to the height of three. Now at a time tree can grow in only one direction(path) and that path might have max no of nodes among all other paths and since our function has to cover those nodes with the help of function call it will call the those number of nodes
Hi, NeetCode, Just curious, was your website created by using html, css and js, or you created by using website builder? If you build it by using html etc, how long will it take you to finish this? thank you
The solution was easy, tbh I was reading the problem, and at first it sounded like it just wanted the nodes where the value was greater than the root, but that wouldn't really make much sense lol
I always feel like if you use nonlocal in helper functions, it'll make your life a ton easier... # 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 goodNodes(self, root: TreeNode) -> int: cnt=0 def helper(root,max_val): nonlocal cnt if not root: return max_val=max(max_val,root.val) if root.val>=max_val: cnt+=1 helper(root.left,max_val) helper(root.right,max_val) helper(root,root.val) return cnt
assume you haven't figure out yet lol, since we are doing dfs, and the max no. of method call frames that can exist on stack is the max(height of tree), which is log(Node)
same code but: Runtime: 272 ms, faster than 37.86% of Python3 online submissions for Count Good Nodes in Binary Tree. Memory Usage: 33.6 MB, less than 13.16% of Python3 online submissions for Count Good Nodes in Binary Tree.
🌲 TREE PLAYLIST: ruclips.net/video/OnSn2XEQ4MY/видео.html
I cannot thank you enough for your videos . They are crisp and easy to follow. For me , your channel become the one stop for all my learning .Using Python simplified even further.
Right after you explained the problem in the first 3min I understood it immediately and realized I needed to just keep track of the max value in the current path.
Looking at your solution, seems I figured it out correctly, thank you man. Liked
How to track max value
btw, where are you from?
I actually got this one without looking at any hints! 🙌Doing all of the previous BST problems beforehand helped greatly.
Alternative using nonlocal
good = 0
def dfs(node, parent):
nonlocal good
if not node: return
if node.val >= parent:
good += 1
max_ = max(parent, node.val)
dfs(node.left, max_)
dfs(node.right, max_)
dfs(root, root.val)
return good
this is pretty good, thanks
So simple and easy the way you did it! I was using a Set and adding each good node to my set, but counting good node is so much easier the way you did it. Thanks for the vid as always!
Can be done easily with BFS as well. There is also no rule against updating the node values, so I used BFS and every time I added a new node to the queue I updated that nodes value if it was < root->val
I did the same, but I used extraspace. Used a array to store the path and update count only if the last element of the array is the max element. It pretty much runs the same!
class Solution:
def goodNodes(self, root: TreeNode) -> int:
count = 0
def dfs(root,res):
nonlocal count
if not root: return res
res.append(root.val)
if max(res) == res[-1]: count += 1
dfs(root.left,res)
dfs(root.right,res)
res.pop()
return res
dfs(root,[])
return count
i performed a level order traversal and was pushing the node's value if it was greater than max value else i was just pushing the max value for both subtrees(if current node value was greater than max) i just incremented the counter
Nice recursive solution, but this can be more intuitive- kind of similar to LCS prob
class Solution {
public int goodNodes(TreeNode root) {
if (root == null) return 0;
return helper(root,root.val);
}
public static int helper(TreeNode root, int max){
if (root == null) return 0;
if (root.val >= max){
return 1 + helper(root.left,Math.max(root.val,max)) + helper(root.right,Math.max(root.val,max));
} else {
return helper(root.left,max) + helper(root.right,max);
}
}
}
Great solution,
Congratulations on 10k subscribers!!
Thanks!
a year later and he's at almost 300k subscribers
and now he is at 699K 😂
If you add 'res' as a parameter of your dfs function, only one stack frame will be used irrespective of how many times dfs is called recursively because of compiler optimization called "tail recursion"
python doesn't optimize tail recursion
Great explanation. Caught the idea in between just by your explanation. And congratulations on 10 K
Its 330K now
It’s almost 600K now 🎉
int helper(TreeNode* root, int prev){
if(root==NULL)
return 0;
if(root->val>=prev)
return 1+helper(root->right,root->val)+helper(root->left,root->val);
else
return helper(root->right,prev)+helper(root->left,prev);
}
int goodNodes(TreeNode* root) {
return helper(root,INT_MIN);
}
C++ implementation
Done Thanks
Similar approach to verifying binary tree, doing a “pre-order- traversal and passing max encountered node from root until now to each recursive call
Why is the space complexity O(logN) or the height of the tree?
because in worst case our function can call max number of function calls that are equal to the height of three. Now at a time tree can grow in only one direction(path) and that path might have max no of nodes among all other paths and since our function has to cover those nodes with the help of function call it will call the those number of nodes
Hi, NeetCode, Just curious, was your website created by using html, css and js, or you created by using website builder? If you build it by using html etc, how long will it take you to finish this? thank you
Yeah i built it from scratch, i talk about it in this video: ruclips.net/video/4G5t1HwHQD4/видео.html
The solution was easy, tbh I was reading the problem, and at first it sounded like it just wanted the nodes where the value was greater than the root, but that wouldn't really make much sense lol
The another one problem I could come up with myself. But as always I watch your videos to find more smart solution
I always feel like if you use nonlocal in helper functions, it'll make your life a ton easier...
# 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 goodNodes(self, root: TreeNode) -> int:
cnt=0
def helper(root,max_val):
nonlocal cnt
if not root:
return
max_val=max(max_val,root.val)
if root.val>=max_val:
cnt+=1
helper(root.left,max_val)
helper(root.right,max_val)
helper(root,root.val)
return cnt
yea and you can also do the same using self:
self.cnt = 0
then every where inside the helper function use self.cnt = ...
Thank you for your video! Well-explained and it's amazing!
I kind of wanted to hear what your neighbors were yelling about lol
“No one solves that under 30 mins”
i am yelling too because its hard to do tree questions with recursion🙃🙃
Congrats on 10K !! can you share from where you get the latest questions asked in FAANG
Мир тебе за твой труд!
Thanks man
wow i am speechless, crazy ! You a god!
Thanks a lot
RecursionError: maximum recursion depth exceeded in comparison
Does anyone know why the space complexity is logarithmic?
assume you haven't figure out yet lol, since we are doing dfs, and the max no. of method call frames that can exist on stack is the max(height of tree), which is log(Node)
good job bro!
Kudos on 10k !!!❤️❤️
he is on 103K subscribers rn !
@@chiamakabrowneyes 155k now. He's growing like nuts. Fully deserved
I think this question should be labeled as "Easy" instead of "Medium" .
It is medium because you can do different approaches with it. If you can do brute force and pass, it could be easy
Yeah all you have to do to pass it is basically just traverse a tree. There are easy questions which are more complex than this
same code but:
Runtime: 272 ms, faster than 37.86% of Python3 online submissions for Count Good Nodes in Binary Tree.
Memory Usage: 33.6 MB, less than 13.16% of Python3 online submissions for Count Good Nodes in Binary Tree.
U a God
Do both iterative and recursive approaches in future
how about Please Do both iterative and recursive approaches in future. Hes doing you a favor.
why it is so easy to you😭
Umm no ...I am not checking interviewing.io ...... I find neetcode better!