Count Good Nodes in Binary Tree

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.

Examples

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

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]

Approach 1: DFS with Path Maximum

Algorithm

Use depth-first search to traverse the tree while keeping track of the maximum value encountered in the current path from root.

Steps:

1. Start DFS from root with initial maximum value as root’s value
2. For each node, check if current node’s value is >= current maximum
3. If yes, increment good nodes count and update maximum
4. Recursively traverse left and right subtrees
5. Return total count of good nodes

Implementation

Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def goodNodes(root):
    """
    Count good nodes using DFS with path maximum tracking
    Time: O(n)
    Space: O(h) where h is height of tree
    """
    def dfs(node, max_val):
        if not node:
            return 0
        
        # Check if current node is good
        count = 1 if node.val >= max_val else 0
        
        # Update maximum value for children
        new_max = max(max_val, node.val)
        
        # Recursively count good nodes in subtrees
        count += dfs(node.left, new_max)
        count += dfs(node.right, new_max)
        
        return count
    
    return dfs(root, root.val)

Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, root.val);
    }
    
    private int dfs(TreeNode node, int maxVal) {
        if (node == null) {
            return 0;
        }
        
        // Check if current node is good
        int count = (node.val >= maxVal) ? 1 : 0;
        
        // Update maximum value for children
        int newMax = Math.max(maxVal, node.val);
        
        // Recursively count good nodes in subtrees
        count += dfs(node.left, newMax);
        count += dfs(node.right, newMax);
        
        return count;
    }
}

Complexity Analysis

• Time Complexity: O(n) where n is the number of nodes in the tree
• Space Complexity: O(h) where h is the height of the tree (recursion stack)

Key Insights

1. Path Maximum Tracking: The key insight is to track the maximum value in the current path from root
2. Root is Always Good: The root node is always considered good since it has no ancestors
3. DFS Traversal: Any traversal order works, but DFS is most natural for path-based problems
4. Recursive vs Iterative: Both approaches have the same time complexity but different space characteristics

Edge Cases

1. Single node: Root is always good, return 1
2. All decreasing values: All nodes are good
3. All increasing values: Only root is good
4. Negative values: Handle negative values correctly
5. Deep tree: Ensure recursion doesn’t cause stack overflow

Test Cases

# Test cases
# Example 1: [3,1,4,3,null,1,5] -> 4
# Example 2: [3,3,null,4,2] -> 3
# Example 3: [1] -> 1

Follow-up Questions

1. Path Sum: Find the sum of all good nodes
2. Good Paths: Find all paths that contain only good nodes
3. Minimum Good Nodes: Find the minimum number of nodes to make all paths good
4. Good Subtree: Find the largest subtree where all nodes are good

Common Mistakes

1. Incorrect comparison: Using > instead of >= for good node check
2. Not updating maximum: Forgetting to update max value for children
3. Root handling: Not properly handling the root node case
4. Path tracking: Not correctly tracking the path maximum

Interview Tips

1. Start with examples: Walk through the examples to understand the problem
2. Clarify definition: Make sure you understand what makes a node “good”
3. Think about traversal: Consider which traversal order makes sense
4. Handle edge cases: Always consider single node and null cases
5. Discuss optimization: Mention both recursive and iterative approaches