Microsoft's Most Asked Question 2021 - Count Good Nodes in a Binary Tree - Leetcode 1448 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: neetcode.io/problems/count-go...
0:00 - Read the problem
1:40 - Drawing Explanation
5:21 - Coding Explanation
leetcode 1448
This question was identified as a microsoft interview question from here: github.com/xizhengszhang/Leet...
#binary #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🌲 TREE PLAYLIST: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@surepasu]

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.

[@kuoyulu6714]

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!

[@chenjus]

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.

[@The6thProgrammer]

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

[@ziontan4402]

Thank you for your video! Well-explained and it's amazing!

[@symbol767]

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

[@rajdeepchakraborty7961]

How to track max value

[@rajdeepchakraborty7961]

btw, where are you from?

[@piyusharyaprakash4365]

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

[@neel1901]

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

[@arpanbanejee5143]

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); } } }

[@davidmwangi4312]

Great solution,

[@abhinaygupta]

Great explanation. Caught the idea in between just by your explanation. And congratulations on 10 K

[@TaiChiSWAG]

Its 330K now

[@hrushikway]

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

[@shashankbarole]

Congratulations on 10k subscribers!!

[@NeetCode]

Thanks!

[@leeroymlg4692]

a year later and he's at almost 300k subscribers

[@natnaelzewdu4289]

and now he is at 699K 😂

[@hemantkapoor6777]

wow i am speechless, crazy ! You a god!

[@muzaffartursunov324]

good job bro!

[@tarunsethi6041]

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"

[@ranvirchhina5179]

python doesn't optimize tail recursion

[@edwardteach2]

U a God

[@saketsingh1055]

i am yelling too because its hard to do tree questions with recursion🙃🙃

[@yoyo8293]

Congrats on 10K !! can you share from where you get the latest questions asked in FAANG

[@huangCAnerd]

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

[@mostinho7]

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

[@nikhildinesan5259]

Kudos on 10k !!!❤️❤️

[@chiamakabrowneyes]

he is on 103K subscribers rn !

[@farazahmed7]

@@chiamakabrowneyes 155k now. He's growing like nuts. Fully deserved

[@MrACrazyHobo]

I kind of wanted to hear what your neighbors were yelling about lol

[@bernardoramirez1759]

“No one solves that under 30 mins”

[@HyunBinKim-yo9fx]

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

[@kanishkameta5377]

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

[@jonaskhanwald566]

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.

[@yijingzhang3191]

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

[@jonaskhanwald566]

Do both iterative and recursive approaches in future

[@CEOofTheHood]

how about Please Do both iterative and recursive approaches in future. Hes doing you a favor.

[@rommeltito123]

Umm no ...I am not checking interviewing.io ...... I find neetcode better!