Count Good Nodes in Binary Tree

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.val. Return the number of good nodes in the binary tree.

Example 1

Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Good nodes are 3 (root), 4, 3 (left child of 1), and 5. Node 1 is not good because 3 > 1 on its path.

Example 2

Input: root = [3,3,null,4,2] Output: 3 Explanation: Good nodes are 3 (root), 3 (left child), and 4. Node 2 is not good because max on path is 3 > 2.

Constraints:

1 <= Number of nodes <= 10⁵
-10⁴ <= Node.val <= 10⁴

Solution: DFS with Max Ancestor
Complexity Analysis

Solution: DFS with Max Ancestor

Perform a pre-order DFS, passing the maximum value seen so far on the path from root to the current node (maxSoFar). A node is good if its value is greater than or equal to maxSoFar. Update maxSoFar before recursing on children.

Algorithm:

Start DFS at root with maxSoFar = Integer.MIN_VALUE.
At each node: if node.val >= maxSoFar, increment good count.
Update maxSoFar = Math.max(maxSoFar, node.val).
Recurse on left and right children with updated maxSoFar.

Java

public int goodNodes(TreeNode root) {
    return dfs(root, Integer.MIN_VALUE);
}

private int dfs(TreeNode node, int maxSoFar) {
    if (node == null) return 0;

    int count = 0;
    if (node.val >= maxSoFar) {
        count = 1; // this node is good
    }

    int newMax = Math.max(maxSoFar, node.val);
    count += dfs(node.left,  newMax);
    count += dfs(node.right, newMax);
    return count;
}

Trace through Example 1: root = [3,1,4,3,null,1,5]

Node	maxSoFar	val >= max?	Good?
3 (root)	-∞	3 >= -∞	Yes
1	3	1 >= 3? No	No
3 (left of 1)	3	3 >= 3	Yes
4	3	4 >= 3	Yes
1 (left of 4)	4	1 >= 4? No	No
5	4	5 >= 4	Yes

Total good nodes = 4.

Complexity Analysis

Time: O(n). Every node is visited exactly once.
Space: O(h). Recursion stack depth equals the tree height h.