🌲 TREE PLAYLIST: kzbin.info/www/bejne/hZ-2n2WOerZng7s
@surepasu3 жыл бұрын
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.
@kuoyulu671410 ай бұрын
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!
@chenjus3 жыл бұрын
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
@ladydimitrescu1155 Жыл бұрын
this is pretty good, thanks
@stylisgamesАй бұрын
I actually got this one without looking at any hints! 🙌Doing all of the previous BST problems beforehand helped greatly.
@The6thProgrammer9 ай бұрын
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
@ziontan44023 жыл бұрын
Thank you for your video! Well-explained and it's amazing!
@symbol7672 жыл бұрын
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
@rajdeepchakraborty796113 күн бұрын
How to track max value
@rajdeepchakraborty796113 күн бұрын
btw, where are you from?
@piyusharyaprakash436511 ай бұрын
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
@neel19014 ай бұрын
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
@arpanbanejee51432 жыл бұрын
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); } } }
@davidmwangi43122 жыл бұрын
Great solution,
@abhinaygupta3 жыл бұрын
Great explanation. Caught the idea in between just by your explanation. And congratulations on 10 K
@TaiChiSWAG Жыл бұрын
Its 330K now
@hrushikway9 ай бұрын
It’s almost 600K now 🎉
@IK-xk7ex Жыл бұрын
The another one problem I could come up with myself. But as always I watch your videos to find more smart solution
@shubham900100 Жыл бұрын
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
@malakggh Жыл бұрын
yea and you can also do the same using self: self.cnt = 0 then every where inside the helper function use self.cnt = ...
@aliciama1745 Жыл бұрын
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
@NeetCode Жыл бұрын
Yeah i built it from scratch, i talk about it in this video: kzbin.info/www/bejne/aniYpWR-rK2EepY
@shashankbarole3 жыл бұрын
Congratulations on 10k subscribers!!
@NeetCode3 жыл бұрын
Thanks!
@leeroymlg4692 Жыл бұрын
a year later and he's at almost 300k subscribers
@natnaelzewdu42893 ай бұрын
and now he is at 699K 😂
@hemantkapoor6777 Жыл бұрын
wow i am speechless, crazy ! You a god!
@muzaffartursunov3247 ай бұрын
good job bro!
@tarunsethi60417 ай бұрын
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"
@ranvirchhina51797 ай бұрын
python doesn't optimize tail recursion
@edwardteach22 жыл бұрын
U a God
@saketsingh10552 жыл бұрын
i am yelling too because its hard to do tree questions with recursion🙃🙃
@yoyo82933 жыл бұрын
Congrats on 10K !! can you share from where you get the latest questions asked in FAANG
@huangCAnerd2 жыл бұрын
Why is the space complexity O(logN) or the height of the tree?
@clashwidzack7298 Жыл бұрын
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
@mostinho72 жыл бұрын
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
@nikhildinesan52593 жыл бұрын
Kudos on 10k !!!❤️❤️
@chiamakabrowneyes2 жыл бұрын
he is on 103K subscribers rn !
@farazahmed72 жыл бұрын
@@chiamakabrowneyes 155k now. He's growing like nuts. Fully deserved
@MrACrazyHobo3 жыл бұрын
I kind of wanted to hear what your neighbors were yelling about lol
@bernardoramirez1759Күн бұрын
“No one solves that under 30 mins”
@HyunBinKim-yo9fx2 жыл бұрын
Does anyone know why the space complexity is logarithmic?
@chaoluncai4300 Жыл бұрын
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)
@JiaTanchun Жыл бұрын
RecursionError: maximum recursion depth exceeded in comparison
@kanishkameta537728 күн бұрын
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
@jonaskhanwald5663 жыл бұрын
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.
@yijingzhang31912 жыл бұрын
why it is so easy to you😭
@ningzedai9052 Жыл бұрын
I think this question should be labeled as "Easy" instead of "Medium" .
@JohnTosun Жыл бұрын
It is medium because you can do different approaches with it. If you can do brute force and pass, it could be easy
@NihongoWakannai Жыл бұрын
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
@jonaskhanwald5663 жыл бұрын
Do both iterative and recursive approaches in future
@CEOofTheHood3 жыл бұрын
how about Please Do both iterative and recursive approaches in future. Hes doing you a favor.
@rommeltito1232 жыл бұрын
Umm no ...I am not checking interviewing.io ...... I find neetcode better!