55.Count Good Nodes in Binary Tree

MediumTrees · 10/15

Problem

Given the root of a binary tree, a node X is called good if, on the path from the root down to X, there is no node with a value greater than X's value.

Return the number of good nodes. The root is always good, and nodes equal to the path maximum also count as good.

Examples

Input:  root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Good nodes are 3 (root), 4 (path 3 -> 4), 5 (path 3 -> 4 -> 5)
             and the lower 3 (path 3 -> 1 -> 3). Node 1 (under 3) and node 1 (under 4) are not good.

Input:  root = [3,3,null,4,2]
Output: 3
Explanation: 3, 3 and 4 are good; 2 is not because 3 > 2 on its path.

Input:  root = [1]
Output: 1

Constraints

The number of nodes in the binary tree is in the range [1, 10^5].
Each node's value is between [-10^4, 10^4].

💡 Key Insight

Whether a node is good depends only on the maximum value on its root path, not on the whole path. So pass that single number down during a traversal: a node is good iff node.val >= maxSoFar, and its children receive max(maxSoFar, node.val). One pass, O(n).

Brute Force (Store the Whole Path)

TimeO(n · h)SpaceO(h)

Intuition

Literally follow the definition: keep the full root-to-node path in a list during DFS, and for each node scan the path to see if any ancestor is larger.

Algorithm

DFS with a path list.
At each node, scan path; if no value exceeds node.val, count it.
Push node.val onto path, recurse into both children, then remove it (backtrack).

Visualization

root = [3,1,4,3,null,1,5]

node 3, path []        -> good
node 1, path [3]       -> 3 > 1, not good
node 3, path [3,1]     -> no value > 3, good
node 4, path [3]       -> good
node 1, path [3,4]     -> not good
node 5, path [3,4]     -> good
total = 4

Code

java

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, new ArrayList<>());
    }

    private int dfs(TreeNode node, List<Integer> path) {
        if (node == null) {
            return 0;
        }
        boolean good = true;
        for (int ancestor : path) {
            if (ancestor > node.val) {
                good = false;
                break;
            }
        }
        path.add(node.val);
        int count = (good ? 1 : 0) + dfs(node.left, path) + dfs(node.right, path);
        path.remove(path.size() - 1); // backtrack
        return count;
    }
}

Complexity

Time: O(n · h) — each node scans a path of length up to h; O(n²) for a skewed tree.
Space: O(h) — the path list and recursion stack.

BFS with (Node, Max) Pairs

TimeO(n)SpaceO(w)

Intuition

Replace the path with its only relevant summary — its maximum. Store (node, maxOnPathAbove) in a queue. When polling, decide goodness in O(1) and enqueue children with the updated maximum.

Algorithm

Enqueue (root, Integer.MIN_VALUE).
While the queue is not empty, poll (node, max):
- If node.val >= max, increment count.
- newMax = max(max, node.val); enqueue non-null children with newMax.
Return count.

Visualization

queue: (3, -inf)                     3 >= -inf good   count 1
       (1, 3), (4, 3)                1 < 3            count 1
                                     4 >= 3 good      count 2
       (3, 3), (1, 4), (5, 4)        3 >= 3 good      count 3
                                     1 < 4            count 3
                                     5 >= 4 good      count 4

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> maxes = new ArrayDeque<>();
        nodes.offer(root);
        maxes.offer(Integer.MIN_VALUE);
        int count = 0;
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            int max = maxes.poll();
            if (node.val >= max) {
                count++;
            }
            int newMax = Math.max(max, node.val);
            if (node.left != null) {
                nodes.offer(node.left);
                maxes.offer(newMax);
            }
            if (node.right != null) {
                nodes.offer(node.right);
                maxes.offer(newMax);
            }
        }
        return count;
    }
}

Complexity

Time: O(n) — each node processed once with O(1) work.
Space: O(w) — the queue holds one level of pairs.

DFS with Running MaxOptimal

TimeO(n)SpaceO(h)

Intuition

The same idea as Approach 2, expressed recursively. The running maximum is passed as a parameter, so each call automatically "forgets" values from sibling branches — no backtracking needed. The code is a few lines and uses O(h) space.

Algorithm

dfs(node, maxSoFar): if node is null, return 0.
good = node.val >= maxSoFar ? 1 : 0.
maxSoFar = max(maxSoFar, node.val).
Return good + dfs(node.left, maxSoFar) + dfs(node.right, maxSoFar).
Answer is dfs(root, root.val).

Dry Run

flowchart TD
    A["3<br/>max in = 3 -> good"] --> B["1<br/>max in = 3 -> not good"]
    A --> C["4<br/>max in = 3 -> good"]
    B --> D["3<br/>max in = 3 -> good"]
    C --> E["1<br/>max in = 4 -> not good"]
    C --> F["5<br/>max in = 4 -> good"]

Good nodes: 3, 3, 4, 5 -> answer 4.

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, root.val);
    }

    // maxSoFar = largest value on the path from root to node's parent
    private int dfs(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 + dfs(node.left, nextMax) + dfs(node.right, nextMax);
    }
}

Complexity

Time: O(n) — each node visited once.
Space: O(h) — recursion depth; up to O(n) for a skewed tree.

Complexity Comparison

Approach	Time	Space
Brute Force (Store the Whole Path)	O(n · h)	O(h)
BFS with (Node, Max) Pairs	O(n)	O(w)
DFS with Running Max	O(n)	O(h)

Common Pitfalls

Using > instead of >= — a node equal to the path maximum is still good (the lower 3 in example 1).
Updating a shared/global max instead of passing it down; values from one branch then leak into the sibling branch.
Initialising the max to 0 — values can be negative, so a negative root would be wrongly marked not good. Use root.val or Integer.MIN_VALUE.
With 10^5 nodes in a skewed tree, recursion depth is 10^5; the BFS version avoids any stack-depth concern.