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
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!
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
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
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
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); }
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
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"
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
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
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: th-cam.com/video/OnSn2XEQ4MY/w-d-xo.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.
I actually got this one without looking at any hints! 🙌Doing all of the previous BST problems beforehand helped greatly.
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?
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!
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
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 think this solution is a bit easier to read.
class Solution:
def goodNodes(self, root: TreeNode) -> int:
self.res = 0
def dfs(root,maxVal):
if(root == None):
return
if(root.val >= maxVal):
self.res +=1
maxVal = max(maxVal, root.val)
dfs(root.left,maxVal)
dfs(root.right,maxVal)
dfs(root,root.val)
return self.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
Congratulations on 10k subscribers!!
Thanks!
a year later and he's at almost 300k subscribers
and now he is at 699K 😂
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
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
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,
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
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
Thank you for your video! Well-explained and it's amazing!
The another one problem I could come up with myself. But as always I watch your videos to find more smart solution
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: th-cam.com/video/4G5t1HwHQD4/w-d-xo.html
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
I kind of wanted to hear what your neighbors were yelling about lol
“No one solves that under 30 mins”
Kudos on 10k !!!❤️❤️
@Chiamaka Udechukwu 155k now. He's growing like nuts. Fully deserved
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 = ...
wow i am speechless, crazy ! You a god!
i am yelling too because its hard to do tree questions with recursion🙃🙃
Thanks a lot
Thanks man
Congrats on 10K !! can you share from where you get the latest questions asked in FAANG
good job bro!
Мир тебе за твой труд!
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)
U a God
RecursionError: maximum recursion depth exceeded in comparison
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.
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!