You are handed a binary tree and asked to count the nodes that are “good”: nothing on the path from the root is greater than the node itself. A review comment said “just check each node against its parent.” That accepts this shape:

      3
     /
    1
     \
      2

2 is greater than 1. The parent check passes. 2 sits under 3, so it is also supposed to be at least 3. It is not. Only the root is good.

A node is good only if its value is at least the maximum on the path from the root. The binary tree post owns shape and traversals. Validate BST carries (low, high) down the same walk; here the bound is a single running max, and the test is >=. A grandchild cannot hide behind a small parent.

The problem

Given the root of a binary tree, return how many nodes are good — no node on the path from the root to that node has a strictly greater value. The root is always good. An empty tree is 0.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees:

      3
     / \
    1   4
   /   / \
  3   1   5     →  4

      3
     /
    1
     \
      2         →  1

[]              →  0
[1]             →  1

Note: Checking node.val >= parent.val is necessary and not sufficient. The test is against every ancestor, not just the parent. Equals on the running max still counts: the left-left 3 under root 3 is good.

Scan the path at every node is the honest brute force

At each node, walk back toward the root (a parent pointer, or the path list you already built) and look for a strictly greater value. None found: the node is good. Correct. Quadratic on a spine: each of n nodes rescans up to h ancestors.

int goodNodesBrute(TreeNode root) {
    return brute(root, new ArrayList<>());
}

int brute(TreeNode node, List<Integer> path) {
    if (node == null) {
        return 0;
    }
    int good = 1;
    for (int v : path) {
        if (v > node.val) {
            good = 0;
            break;
        }
    }
    path.add(node.val);
    int total = good + brute(node.left, path) + brute(node.right, path);
    path.remove(path.size() - 1);
    return total;
}

At a dozen nodes this is a rounding error. At a million-node spine you still visit everyone, plus a scan proportional to depth at each visit. The intended answer never keeps the path: the path reduces to its maximum.

Carry the running max

At the root the running max is unbounded below. Seed it with Integer.MIN_VALUE so a MIN_VALUE root still satisfies >= and counts. When you leave a node, children inherit max(maxSoFar, node.val). A node is good when node.val >= maxSoFar.

node 3, maxSoFar = MIN_VALUE   3 >= MIN_VALUE  good, children get 3
node 1, maxSoFar = 3           1 >= 3? no,     children get 3
node 3, maxSoFar = 3           3 >= 3          good
node 4, maxSoFar = 3           4 >= 3          good, children get 4
node 1, maxSoFar = 4           1 >= 4? no
node 5, maxSoFar = 4           5 >= 4          good

Count is 4: the root 3, the left-left 3, 4, and 5. Both 1s lose to an ancestor.

Validate BST cannot use Integer.MIN_VALUE as “no lower bound”: node.val <= low then rejects a legal MIN_VALUE root. Here the test is >=, so equality saves that root. If you dislike the sentinel, count the root as 1 and start the children at root.val.

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

int walk(TreeNode node, int maxSoFar) {
    if (node == null) {
        return 0;
    }
    int good = node.val >= maxSoFar ? 1 : 0;
    int nextMax = Math.max(maxSoFar, node.val);
    return good + walk(node.left, nextMax) + walk(node.right, nextMax);
}

Time is O(n) — each node is checked once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack of (node, maxSoFar) is the same bound without blowing the JVM stack.

Empty root: the first null check returns 0. A single node: val >= MIN_VALUE, both children null, return 1. No extra branch.

What interviewers usually poke next

  • Parent-only check. Draw the 3 / 1 / 2 counterexample. That drawing is the whole point of this question.
  • int extrema. Integer.MIN_VALUE as the seed works here because of >=. Name why the same sentinel is a trap in Validate BST. Prefer counting the root first if they flinch at the seed.
  • Strict greater. If “good” meant strictly greater than every ancestor, a node equal to the running max would drop, and a MIN_VALUE root with a MIN_VALUE seed would fail. Name the policy before you edit >=.
  • List the nodes, not the count. Same walk; append instead of adding 1. Do not start allocating a path list inside goodNodes.

You are done with this problem when you can reject 3 / 1 / 2 without scanning ancestors, and you can explain why Integer.MIN_VALUE as a seed works here and fails in Validate BST.