Count Good Nodes in Binary Tree

medium tree dfs

Problem

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.

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_;
}

Explanation

A node is good if no node on the path from the root down to it is bigger than it. The neat idea is to do one DFS that carries the largest value seen so far, mx, down each path.

When we arrive at a node, we compare its value against mx. If n.val >= mx, nothing above it was larger, so it is good and we bump count. Note the >=: a node equal to the running max still counts.

Before recursing into the children, we update the running max to m = max(mx, n.val) and pass that down both sides. Each branch gets its own path-max, since what's "above" depends on the route taken. We start the root with -infinity so the root is always good.

Example: tree [3, 1, 4, 3, _, 1, 5]. Root 3 is good (max becomes 3). Its right child 4 is ≥ 3, good (max 4); below it 5 is ≥ 4, good. On the left side the second 3 equals the running max 3, so it is also good. That makes 4 good nodes.

Because the running max travels down with the recursion, a single linear pass correctly counts every good node.

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