Solutions

# Pass the current max value down the tree and compare it with the current node's value. If the current node's value is greater than or equal to the max value, it's a good node.
# trees

# DFS - O(n) time, O(n) space
class Solution:
    def __init__(self):
        self.count = 0

    def goodNodes(self, root: TreeNode) -> int:
        self.helper(root, -101)
        return self.count
        

    def helper(self, node: TreeNode, max_so_far: int):
        if not node:
            return

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

        max_so_far = max(max_so_far, node.val)

        self.helper(node.left, max_so_far)
        self.helper(node.right, max_so_far)


# BFS - O(n) time, O(n) space
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        count = 0
        queue = [(root, -101)]

        while queue:
            node, max_so_far = queue.pop(0)

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

            max_so_far = max(max_so_far, node.val)

            if node.left:
                queue.append((node.left, max_so_far))
            if node.right:
                queue.append((node.right, max_so_far))

        return count