Leetcode 1448. Count Good Nodes in Binary Tree

Problem

Leetcode 1448 - Count Good Nodes in Binary Tree

Example:

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.

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

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

Approach

Since we’re only counting the nodes to be “good” if the node in the path from root to X there are no nodes with a value greater than X, we can use DFS to solve this problem.

Using DFS, we can keep track of the max_value of the nodes along the path, and if our child value is more than equal to max_value, then it’s a good node, else it’s a bad node.

Here is the Python code for the solution:

class Solution:
    def goodNodes(self, root: TreeNode) -> int:   
        def dfs(root, max_val):
            if not root:
                return 0

            res = 1 if root.val >= max_val else 0
            max_val = max(max_val, root.val)
            res += dfs(root.left, max_val)
            res += dfs(root.right, max_val) 

            return res
        
        return dfs(root, root.val)    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$