Difficulty: MediumTrees

Count Good Nodes in Binary Tree

Problem in Plain English

Given the root of a binary tree, count the nodes whose value is greater than or equal to every value on the path from the root. The root itself always counts as good.

Problem Statement

A node X in a binary tree is good when no node on the path from the root down to X holds a value greater than X.

Given the root of a binary tree, return the total number of good nodes. The root has no ancestors above it, so it is always good.

Constraints

1 <= number of nodes <= 10^5
-10^4 <= Node.val <= 10^4

Examples

Example 1

Input: root = [3,1,4,3,null,1,5]
Output: 4

3, the leaf 3, 4, and 5 each match or beat every ancestor above them, while 1 and the second 1 do not.

Example 2

Input: root = [3,3,null,4,2]
Output: 3

Both 3 nodes and 4 are good, but 2 sits below a larger 3.

Example 3

Input: root = [1]
Output: 1

The root is good by definition.

Example 4

Input: root = [-3,-4,-2]
Output: 2

The root -3 is good. The left child -4 is below -3 and fails; the right child -2 exceeds -3 and passes. Starting a maximum at zero would incorrectly reject every node.

Example 5

Input: root = [3,9,4]
Output: 3

The root 3 and both children are good: each child only compares with ancestor 3. Visiting 9 first must not raise the threshold for its sibling 4.

Intuition

A good node ties or sets a record along its own root-to-node path. Only its ancestors matter: a larger value in a sibling subtree cannot disqualify it. In Example 1, the leaf 3 below 1 is good because its ancestors are 1 and 3, while the leaf 1 below 4 is not. Checking every ancestor separately repeats shared paths; carrying the path maximum gives each node the whole comparison in one number. Equal values count, and the starting maximum must handle negative values.

Approaches

Path Check Per Node

Solution Details

Reveal Path Check Per Node: intuition, complexity, and code

Intuition

First record the parent of every node. Reject a candidate below the root value immediately, since the root is an ancestor of every nonroot node; otherwise walk upward through its ancestors. Reject immediately on finding a larger ancestor: one counterexample is enough. If the walk reaches beyond the root, every ancestor passed. In Example 1, the leaf 3 passes ancestors 1 and 3; the leaf 1 below 4 already fails against root 3. This direct check is easy to justify, but repeated successful walks through shared prefixes can still take quadratic time.

Step-by-Step Logic

Return zero for an empty root as a defensive extension. Otherwise use an explicit stack to record every node and its parent. Push right before left to obtain left-first preorder: Example 1 records root 3, left 1, leaf 3, right 4, leaf 1, then leaf 5.
For each recorded node, first skip it if it is below root.val; both 1-valued nodes in Example 1 fail this preliminary check. Otherwise start at its parent with good set to true. The root 3 begins at null, so its check succeeds immediately.
While an ancestor exists, compare its value with the candidate value. If the ancestor is larger, set good to false and stop; this catches larger internal ancestors even when the candidate passed the root, as root [3,9,null,4] demonstrates: 4 passes root 3 but fails at parent 9.
Otherwise move to the next parent and repeat until null. The leaf 3 passes 1 then 3, right 4 passes 3, and leaf 5 passes 4 then 3. Equality is allowed.
Add one for each successful check, then return count. The six verdicts are yes, no, yes, yes, no, yes, producing 4 without changing tree values or links.

Why It Works

The initial traversal records each node once and assigns its actual parent, so repeatedly following parent links visits exactly that node's ancestors and then stops at null. The preliminary comparison against the root rejects only candidates below a known ancestor. A node rejected by a larger ancestor during the upward walk violates the definition and cannot be good. A node that reaches null has no larger ancestor anywhere on its root path, so it is good. Equality never causes rejection. The root starts with no parent and therefore passes. Checking each recorded node once and increasing the count precisely for successful checks returns exactly the number of good nodes. Parent keys use node identity rather than values, so equal-valued nodes keep distinct ancestor paths.

Dry Run

Path Check Per Node: variable states at each step
Phase / candidate	Ancestor before -> after	Comparison / action	good	count before -> after
Initialize parent traversal	parent[root 3] = null	stack [root 3], bottom -> top; nodes []	pending	0 -> 0
Pop root 3	parents[right 4,left 1] = root 3	stack [right 4,left 1]; nodes [root 3]	pending	0 -> 0
Pop left 1	parent[leaf 3] = left 1	stack [right 4,leaf 3]; nodes append left 1	pending	0 -> 0
Pop leaf 3	no new parent links	stack [right 4]; nodes append leaf 3	pending	0 -> 0
Pop right 4	parents[leaf 5,leaf 1] = right 4	stack [leaf 5,leaf 1]; nodes append right 4	pending	0 -> 0
Pop leaf 1	no new parent links	stack [leaf 5]; nodes append leaf 1	pending	0 -> 0
Pop leaf 5	no new parent links	stack []; nodes append leaf 5	pending	0 -> 0
Root 3	null -> null	no ancestors; finish	true	0 -> 1
Left 1	root precheck -> stop	1 < root 3; reject before climb	false	1 -> 1
Leaf 3 below 1	left 1 -> root 3	1 <= 3; climb	true	1 -> 1
Same leaf 3	root 3 -> null	3 <= 3; climb and finish	true	1 -> 2
Right 4	root 3 -> null	3 <= 4; climb and finish	true	2 -> 3
Leaf 1 below 4	root precheck -> stop	1 < root 3; reject before climb	false	3 -> 3
Leaf 5	right 4 -> root 3	4 <= 5; climb	true	3 -> 3
Same leaf 5	root 3 -> null	3 <= 5; climb and finish	true	3 -> 4
Return	all six nodes checked	return 4	finished	4 -> 4

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be node count and h tree height in nodes. Recording parents takes O(n) time; subsequent checks perform at most the sum of node depths, bounded by O(nh). An equal-valued chain forces every walk to reach the root and gives n(n-1)/2 ancestor comparisons, proving O(n²) worst-case time. The preliminary root comparison makes a chain whose root is 10000 and all descendants are -10000 linear, without walking through the equal-valued intermediate ancestors. The identity parent map and node list retain O(n) entries; the explicit traversal stack holds at most O(h) pending nodes. Java creates O(n) map entries, Python dictionary entries, and JavaScript Map entries; no ancestor-path copies or recursive calls are allocated. The scalar answer uses constant space. The baseline is stack-safe for 100000 nodes but its quadratic worst case is intentionally impractical; use the optimal approach for large successful paths.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.ArrayList;3import java.util.IdentityHashMap;4import java.util.List;5import java.util.Map;6
7class TreeNode {8    int val;9    TreeNode left, right;10    TreeNode(int val) { this.val = val; }11    TreeNode(int val, TreeNode left, TreeNode right) {12        this.val = val; this.left = left; this.right = right;13    }14}15
16class Solution {17    public int goodNodes(TreeNode root) {18        if (root == null) return 0;19        // Identity keys distinguish equal-valued nodes with different ancestors.20        Map<TreeNode, TreeNode> parent = new IdentityHashMap<>();21        List<TreeNode> nodes = new ArrayList<>();22        ArrayDeque<TreeNode> stack = new ArrayDeque<>();23        parent.put(root, null);24        stack.push(root);25        while (!stack.isEmpty()) {26            TreeNode node = stack.pop();27            nodes.add(node);28            if (node.right != null) {29                parent.put(node.right, node);30                stack.push(node.right);31            }32            if (node.left != null) {33                parent.put(node.left, node);34                stack.push(node.left);35            }36        }37        int count = 0;38        for (TreeNode node : nodes) {39            // The root is a known ancestor: reject before a potentially long climb.40            if (node.val < root.val) continue;41            boolean good = true;42            TreeNode ancestor = parent.get(node);43            while (ancestor != null) {44                // One larger ancestor disproves goodness; ties must pass.45                if (ancestor.val > node.val) {46                    good = false;47                    break;48                }49                ancestor = parent.get(ancestor);50            }51            if (good) count++;52        }53        return count;54    }55}

Hints

Hint 1

Compare a node with its ancestors, not with every value in the tree. The root always qualifies.

Hint 2

The ancestors can be summarized by their maximum value. A node equal to that maximum still qualifies.

Hint 3

Carry the maximum in each pending stack entry and update it before pushing children. Use an explicit stack to handle the maximum valid depth.

Edge Cases

A single node is always good, even at value -10000. The public input is nonempty; the snippets additionally return zero for null.
An increasing root-to-leaf chain makes every node good; a strictly decreasing chain makes only the root good.
An all-equal tree makes every node good, since equality is permitted. This is also the parent-check baseline's quadratic worst case on a chain.
Negative values work unchanged when the initial threshold is root.val rather than zero.
A large left-subtree value must not disqualify a smaller good node in the right subtree, as root [3,9,4] demonstrates.
A 100000-node chain requires iterative traversal in these languages; the optimal stack has only one pending node on that shape.

Common Mistakes and Interview Tips

Using one shared maximum across siblings: in [3,9,4], visiting 9 must not make 4 fail.
Comparing with strict greater-than when counting good nodes, which rejects legitimate ties.
Comparing only with the direct parent: in [5,1,null,3], leaf 3 exceeds parent 1 but fails against ancestor 5.
Initializing the maximum to zero, which incorrectly rejects an entirely negative tree.
Using recursion without accounting for the 100000-node depth bound; Python, Java and JavaScript may overflow their call stacks.
Treating the O(n²) parent-check baseline as suitable for every maximum-size input; equal-valued long chains force every ancestor walk to finish.

Key Takeaway

When a root-path predicate depends only on an aggregate such as maximum, minimum or sum, carry that aggregate with each pending node. Update it locally for children so siblings inherit the same prefix state without sharing later changes.