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.

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.

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

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.

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.

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

Constraints:

Contents

Algorithm:

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