Count Good Nodes In Binary Tree - Leetcode Solution

Problem statement:

Given a binary tree, a node is called "good" if it satisfies the following conditions:

1. It is a leaf node.
2. Its value is greater than or equal to the maximum value of any node in its left subtree.
3. Its value is less than or equal to the minimum value of any node in its right subtree.

Return the number of good nodes in the binary tree.

Example:

Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: There are 4 good nodes in the binary tree: 3, 4, 5, and 3 (again).

Solution:

This problem can be solved by traversing the binary tree in a depth-first manner. We can maintain a variable count that stores the number of good nodes we have found so far. Whenever we visit a node during the traversal, we check if it is a good node or not according to the conditions mentioned above.

To check if a node is a good node, we need to keep track of the maximum and minimum values seen so far in its left and right subtrees separately. We can pass these values as parameters to the recursive function that traverses the tree.

We can start by initializing these maximum and minimum values as null for the root node. For each node, we can update the maximum value in its left subtree to the maximum of its current maximum and the value of the current node. Similarly, we can update the minimum value in its right subtree to the minimum of its current minimum and the value of the current node. Then we can check if the current node satisfies the conditions for being a good node by comparing its value with the maximum and minimum values seen so far in its left and right subtrees.

Here is the implementation of this algorithm in Python:

class Solution: def goodNodes(self, root: TreeNode) -> int: return self.countGoodNodes(root, root.val)

def countGoodNodes(self, node, max_so_far):
    if node is None:
        return 0

    count = 0
    if node.val >= max_so_far:
        count += 1
        max_so_far = node.val

    count += self.countGoodNodes(node.left, max_so_far)
    count += self.countGoodNodes(node.right, max_so_far)

    return count

In this implementation, we have defined a recursive function countGoodNodes that takes two parameters: the current node and the maximum value seen so far in the current path. We initialize this maximum value as the value of the root node when we call the function for the first time.

Inside the function, we first check if the current node satisfies the conditions for being a good node. If it does, we add one to the count of good nodes and update the maximum value seen so far to the value of the current node.

Then we recursively call the function for the left and right subtrees of the current node, passing the updated maximum value seen so far. Finally, we return the total count of good nodes found in the tree.

Time complexity: O(N), where N is the number of nodes in the tree. We need to visit each node once during the traversal.

Space complexity: O(H), where H is the height of the tree. The space required by the call stack of the recursive function is proportional to the height of the tree. In the worst case (skewed tree), the height of the tree can be N, so the space complexity would be O(N) in that case.

1