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

0:00 - Read the problem
1:40 - Drawing Explanation
5:21 - Coding Explanation

leetcode 1448

#binary #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[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.

[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

[stylisgames]

I actually got this one without looking at any hints! 🙌Doing all of the previous BST problems beforehand helped greatly.

[symbol]

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

[kanishkameta]

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

[arpanbanejee]

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

}
}

[kuoyulu]

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!

[neel]

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

[shubham]

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

[ThethProgrammer]

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

[piyusharyaprakash]

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

[mostinho]

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

[huangCAnerd]

Why is the space complexity O(logN) or the height of the tree?

[abhinaygupta]

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

[tarunsethi]

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"

[aliciama]

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

[ziontan]

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

[IK-xkex]

The another one problem I could come up with myself. But as always I watch your videos to find more smart solution

[RandomShowerThoughts]

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

[MrACrazyHobo]

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