1448-Count Good Nodes in Binary Tree

Leetcode 75-day challenge

So, the problem I chose for today is: Count Good Nodes in Binary Tree

Before I start explaining the solution to this problem, I assume that the reader of this blog has a basic understanding of how Binary Search Trees (BST) work. If not, you can watch my YouTube video on the topic here:

BST-1 video — from my YouTube channel

Let’s start:

Given a binary tree root, a node X in the tree is named good if in the path from root to X, there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

Taken from Leetcode

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Taken from Leetcode

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

• The number of nodes in the binary tree is in the range [1, 10^5].
• Each node’s value is between [-10^4, 10^4].

Solution:

code snippet — created using ray.so

Here’s a step-by-step explanation:

1. res is a class-level variable used to keep track of the count of good nodes.
2. The goodNodes method is the entry point for counting good nodes in the tree. It initializes the counting process by calling the getGoodNodes method with the root of the tree and the minimum integer value as the starting maximum.
3. The getGoodNodes method is a recursive function that traverses the binary tree in a depth-first manner.
4. At each node, it checks if the current node’s value is greater than or equal to the maximum value found in the path from the root to that node. If so, it updates the maximum value and increments the count of good nodes (res).
5. Then, it recursively calls getGoodNodes on the left and right subtrees, passing the updated maximum value.
6. The count of good nodes (res) is finally returned from the goodNodes method.

And you can find the GitHub gist here

I hope I was able to explain the solution and it’ll help and motivate you to start the challenge as well.

Leetcode challenge

Youtube

LinkedIn

Instagram

For more coding examples check out these blogs:

Day 1: Search in a Binary Search Tree

Day 2: Delete Node in a Binary Search Tree

Day 3: Move Zeroes

Day 4: Is Subsequence