Count Good Nodes in Binary Tree

Problem

A node X is good if no node with a value greater than X.val exists on the path from root to X. Count good nodes.

Key insight: DFS carrying max so far. Node is good if node.val >= max_so_far.

Solutions

// C
int dfs(TreeNode* node, int maxSoFar) {
    if (!node) return 0;
    int good = (node->val >= maxSoFar) ? 1 : 0;
    int newMax = node->val > maxSoFar ? node->val : maxSoFar;
    return good + dfs(node->left, newMax) + dfs(node->right, newMax);
}
int goodNodes(TreeNode* root) { return dfs(root, INT_MIN); }

// C++
int dfs(TreeNode* node, int maxSoFar) {
    if (!node) return 0;
    int good = node->val >= maxSoFar ? 1 : 0;
    int newMax = max(maxSoFar, node->val);
    return good + dfs(node->left, newMax) + dfs(node->right, newMax);
}
int goodNodes(TreeNode* root) { return dfs(root, INT_MIN); }

// Java
public int goodNodes(TreeNode root) {
    return dfs(root, Integer.MIN_VALUE);
}
int dfs(TreeNode node, int maxSoFar) {
    if (node == null) return 0;
    int good = node.val >= maxSoFar ? 1 : 0;
    int newMax = Math.max(maxSoFar, node.val);
    return good + dfs(node.left, newMax) + dfs(node.right, newMax);
}

// JavaScript
function goodNodes(root) {
    function dfs(node, maxSoFar) {
        if (!node) return 0;
        const good = node.val >= maxSoFar ? 1 : 0;
        const newMax = Math.max(maxSoFar, node.val);
        return good + dfs(node.left, newMax) + dfs(node.right, newMax);
    }
    return dfs(root, -Infinity);
}

# Python
def goodNodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0
        good = 1 if node.val >= max_so_far else 0
        new_max = max(max_so_far, node.val)
        return good + dfs(node.left, new_max) + dfs(node.right, new_max)
    return dfs(root, float('-inf'))

Complexity

Time: O(n)
Space: O(h)