Count Good Nodes Along Root Paths

medium tree dfs

Problem

A node is good if no ancestor on the root-to-node path holds a strictly larger value. Count all good nodes with one DFS that carries the running maximum down each path.

Inputtree (level-order) = [3, 1, 4, 3, _, 1, 5]

Output4

Good nodes: 3 (root), 4 (≥ 3), 3 (left subtree, equals max so far), 5 (≥ 4).

tree (level-order, '_' for null)

def good_nodes(root):
    count = 0
    def dfs(n, mx):
        nonlocal count
        if not n: return
        if n.val >= mx: count += 1
        m = max(mx, n.val)
        dfs(n.left, m); dfs(n.right, m)
    dfs(root, float('-inf'))
    return count

function goodNodes(root) {
  let count = 0;
  function dfs(n, mx) {
    if (!n) return;
    if (n.val >= mx) count++;
    const m = Math.max(mx, n.val);
    dfs(n.left, m); dfs(n.right, m);
  }
  dfs(root, -Infinity);
  return count;
}

class Solution {
    int count;
    public int goodNodes(TreeNode root) {
        count = 0;
        dfs(root, Integer.MIN_VALUE);
        return count;
    }
    private void dfs(TreeNode n, int mx) {
        if (n == null) return;
        if (n.val >= mx) count++;
        int m = Math.max(mx, n.val);
        dfs(n.left, m); dfs(n.right, m);
    }
}

int count_;
void dfs(TreeNode* n, int mx) {
    if (!n) return;
    if (n->val >= mx) count_++;
    int m = max(mx, n->val);
    dfs(n->left, m); dfs(n->right, m);
}
int goodNodes(TreeNode* root) {
    count_ = 0;
    dfs(root, INT_MIN);
    return count_;
}

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