Problem Statement

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.

Additional information

• 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].

Example 1:

Input: root = [3, 1, 4, 3, null, 1, 5]

Output: 4

Explanation: * Root Node (3) is always a good node.

• Node 4 -> (3, 4) is the maximum value in the path.
• 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 good, because 3 is higher than it.

Example 3:

Input: root = [1]

Output: 1

Recursive Depth-First Search (DFS) - Optimal

Intuition

To determine if a node is "good", we only need to know one thing about the path leading up to it: the maximum value encountered so far.
If the current node's value is greater than or equal to that maximum, it is a good node!

We can use Depth-First Search (DFS) to traverse the tree. As we go deeper into the branches, we pass down the highest value we've seen on that specific path.

Algorithm

1. Create a helper function dfs(node, max_so_far).
2. Base Case: If node is None, return 0 (no good nodes here).
3. Check if the current node is good:

• If node.val >= max_so_far, this node is good. Count it as 1.
• Otherwise, it's not good. Count it as 0.

4. Update the maximum value for the path going forward: new_max = max(max_so_far, node.val).
5. Recursively call dfs on the left and right children, passing down the new_max.
6. Return the sum of the current node's goodness plus the good nodes found in both subtrees.
7. Call dfs(root, root.val) to start.

def good_nodes(root: TreeNode) -> int:
    def dfs(node, max_so_far):
        if not node:
            return 0
            
        # Is the current node good?
        res = 1 if node.val >= max_so_far else 0
        
        # What is the new max for the children?
        max_so_far = max(max_so_far, node.val)
        
        # Traverse left and right subtrees
        res += dfs(node.left, max_so_far)
        res += dfs(node.right, max_so_far)
        
        return res
        
    return dfs(root, root.val)

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node in the binary tree exactly once. The work done at each node (comparisons and additions) is O(1).

• Space complexity: O(h)

• Reason: The space complexity is determined by the recursion stack. In the worst case (a completely skewed tree), the height h equals n, leading to O(n) space. For a balanced tree, it is O(log n).

Iterative Depth-First Search (DFS)

Intuition

If we want to avoid recursion (perhaps to prevent stack overflow on extremely deep trees), we can use an explicit stack to perform DFS iteratively.
Instead of just pushing nodes onto the stack, we push a tuple containing the node and the max_so_far for the path that led to it.

Algorithm

1. If the root is None, return 0.
2. Initialize a stack with the starting tuple: [(root, root.val)].
3. Initialize a count to 0.
4. While the stack is not empty:

• Pop the current node and the max_so_far from the stack.
• If node.val >= max_so_far, it's a good node. Increment count.
• Update max_so_far = max(max_so_far, node.val).
• If the right child exists, push (node.right, max_so_far) onto the stack.
• If the left child exists, push (node.left, max_so_far) onto the stack.

5. Return count.

def good_nodes(root: TreeNode) -> int:
    if not root:
        return 0
        
    count = 0
    stack = [(root, root.val)]
    
    while stack:
        node, max_so_far = stack.pop()
        
        if node.val >= max_so_far:
            count += 1
            
        max_so_far = max(max_so_far, node.val)
        
        if node.right:
            stack.append((node.right, max_so_far))
        if node.left:
            stack.append((node.left, max_so_far))
            
    return count

Time & Space Complexity

• Time complexity: O(n)

• Reason: Each node is pushed and popped from the stack exactly once.

• Space complexity: O(h)

• Reason: The stack holds at most h elements at any given time, where h is the height of the tree.