Count Good Nodes In Binary Tree Leetcode Problem 1448 [Python]

In this blog post, we are going to tackle the Count Good Nodes In Binary Tree problem, which is categorized as a medium difficulty problem on LeetCode.

This problem is often asked by Microsoft in their interviews, making it a valuable one to master.

We'll provide a Python solution, break down the problem step by step, and explain the reasoning behind our approach.

Problem Overview

The problem statement is as follows:

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

The task is to return the number of good nodes in the binary tree.

Let's take a look at an example to better understand this:

Example 1:

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:

Input:
root = [3,3,null,4,2]

Output:
3

Explanation:
Node 2 -> (3, 3, 2) is not a good node 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].

Now that we understand the problem, let's proceed with the solution.

Understanding the Constraints

Before diving into the solution, let's discuss the constraints provided in the problem statement.

Understanding these constraints is crucial for devising an efficient algorithm.

The first constraint mentions the number of nodes in the binary tree, which can be as large as 10^5. This indicates that we need a solution with a time complexity of O(N) to handle the worst-case scenario efficiently.

The second constraint states that each node's value is between -10^4 and 10^4. This range is manageable, and we won't encounter extremely large or small values.

Now that we have a good grasp of the problem and its constraints, let's proceed with the solution.

Count Good Nodes In Binary Tree LeetCode Problem Solution

We will solve this problem using a depth-first search (DFS) approach.

The idea is to traverse the binary tree and keep track of the maximum value encountered along the path from the root to the current node.

If a node's value is greater than or equal to the maximum value encountered so far, it is considered a "good node."

Here's the Python solution:

View on GitHub ➹

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) -&gt; int:
        def dfs(node, maxVal):
            if not node:
                return 0

            res = 1 if node.val &gt;= maxVal else 0
            maxVal = max(maxVal, node.val)
            res += dfs(node.left, maxVal)
            res += dfs(node.right, maxVal)
            return res

        return dfs(root, root.val)

Let's break down the solution step by step.

1. Bruteforce Approach

We start by defining a TreeNode class that represents a node in the binary tree.
We also define a Solution class to encapsulate our solution method.
The goodNodes method takes the root node of the binary tree as an input and returns the number of good nodes.

2. Depth-First Search (DFS)

We implement a DFS function dfs inside the goodNodes method.

This function recursively explores the binary tree and keeps track of the maximum value encountered along the path from the root to the current node.

If the current node is None (i.e., we've reached a leaf node or an empty subtree), we return 0 because there are no good nodes in this subtree.
We initialize res to 1 if the current node's value (node.val) is greater than or equal to the maxVal passed to this node.

This is because, by definition, the current node is a good node if its value is not less than the maximum value encountered along the path.

We update the maxVal by taking the maximum of the current maxVal and the value of the current node (node.val).
We then recursively call dfs on the left and right children of the current node and add their results to res.

This is how we count good nodes in the left and right subtrees.

Finally, we return the total count of good nodes, which is stored in res.

Time and Space Complexity

Now, let's analyze the time and space complexity of this solution.

Time Complexity: The time complexity of this solution is O(N), where N is the number of nodes in the binary tree.

We visit each node once in a depth-first manner, making it a linear time solution.

Space Complexity: The space complexity is O(H), where H is the height of the binary tree.

In the worst case, the height of the binary tree can be equal to the number of nodes (N), which results in O(N) space complexity.

However, in balanced trees, the space complexity will be closer to O(log(N)).

Reasoning Behind Our Approach

The reasoning behind our approach is straightforward.

We use a depth-first search to traverse the binary tree while keeping track of the maximum value encountered along the path from the root to each node.

If a node's value is greater than or equal to this maximum, it's considered a good node.

By following this approach, we efficiently count the number of good nodes in the binary tree without the need for complex data structures or additional space.

The depth-first search allows us to explore the tree in a structured manner, ensuring that each node is examined once.

Conclusion

In this blog post, we tackled the Count Good Nodes In Binary Tree problem, which is a medium difficulty problem on LeetCode and a commonly asked question by Microsoft.

We provided a Python solution that efficiently counts the number of good nodes in a binary tree by using a depth-first search (DFS) approach.

Our solution has a time complexity of O(N), making it suitable for large trees.

Understanding this problem and its solution is valuable for mastering binary tree traversal and solving similar tree-related problems.

We hope this post has been helpful in breaking down the problem and providing a clear, efficient solution.

If you found this content useful, please consider liking and subscribing to support the our platform.

Feel free to leave comments, ask questions, make suggestions, and share the content

Your engagement is greatly appreciated.

For the original problem statement and to practice the solution, you can visit the Count Good Nodes in Binary Tree LeetCode page.

Happy coding!