Skip to main content
CodePeetCodePeet
CodePeet 250

Count Good Nodes in Binary Tree

MEDIUMProblemSolveExternal Links

Description

Given a binary tree rooted at root, a node X in the tree is called a good node if, along the path from the root to X, there is no node with a value greater than X.

In other words, a node is good when its value is greater than or equal to every ancestor's value on the path from the root down to it. The root node is always considered good because it has no ancestors.

Return the total number of good nodes in the binary tree.

Binary tree with root 3, left child 1 (with left child 3), right child 4 (with children 1 and 5). Good nodes 3, 3, 4, 5 highlighted green; non-good nodes 1, 1 highlighted red.
Binary tree with root 3, left child 1 (with left child 3), right child 4 (with children 1 and 5). Good nodes 3, 3, 4, 5 highlighted green; non-good nodes 1, 1 highlighted red.

Examples

Example 1

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

Output: 4

Explanation: The tree structure is:

        3
       / \
      1   4
     /   / \
    3   1   5
  • Node 3 (root): The root has no ancestors, so it is always good. ✓
  • Node 1 (left child of root): Path is [3 → 1]. Ancestor 3 is greater than 1, so this node is NOT good. ✗
  • Node 4 (right child of root): Path is [3 → 4]. No ancestor exceeds 4 (3 ≤ 4), so it is good. ✓
  • Node 3 (left grandchild): Path is [3 → 1 → 3]. The maximum ancestor value is 3, and 3 ≥ 3, so it is good. ✓
  • Node 1 (right-left grandchild): Path is [3 → 4 → 1]. Ancestor 4 is greater than 1, so NOT good. ✗
  • Node 5 (right-right grandchild): Path is [3 → 4 → 5]. No ancestor exceeds 5 (max is 4), so it is good. ✓

Good nodes: 3, 4, 3, 5 → Total = 4.

Example 2

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

Output: 3

Explanation: The tree structure is:

    3
   /
  3
 / \
4   2
  • Node 3 (root): Always good. ✓
  • Node 3 (left child): Path is [3 → 3]. Maximum ancestor is 3, and 3 ≥ 3, so good. ✓
  • Node 4 (left-left): Path is [3 → 3 → 4]. Maximum ancestor is 3, and 4 ≥ 3, so good. ✓
  • Node 2 (left-right): Path is [3 → 3 → 2]. Maximum ancestor is 3, and 2 < 3, so NOT good. ✗

Good nodes: 3, 3, 4 → Total = 3.

Example 3

Input: root = [1]

Output: 1

Explanation: The tree has only one node — the root with value 1. The root is always good because it has no ancestors. Total = 1.

Constraints

  • 1 ≤ Number of nodes in the binary tree ≤ 10^5
  • -10^4 ≤ Node.val ≤ 10^4

Editorial

Brute Force

Intuition

The definition tells us: a node is good if its value is greater than or equal to every ancestor on its root-to-node path. The most direct way to check this is to literally keep track of the entire path from the root down to the current node.

Imagine you are hiking down a mountain trail that branches at every fork. You carry a notebook where you record the altitude at every point you have passed. When you arrive at a new point, you flip through the entire notebook to find the highest altitude you have recorded. If the current altitude is at least as high as that recorded maximum, this point qualifies as a "peak point". Then you add the current altitude to the notebook and continue.

In tree terms, we perform a depth-first search (DFS). As we descend, we maintain a list (path) containing every ancestor's value from the root down to the current node's parent. At each node, we scan that entire list to find the maximum value. If the current node's value is greater than or equal to that maximum, we count it as good. We add the current value to the path before visiting children, and remove it after returning (backtracking), so the path always reflects the current root-to-node route.

Step-by-Step Explanation

Let's trace through Example 1: root = [3,1,4,3,null,1,5].

Tree:

        3
       / \
      1   4
     /   / \
    3   1   5

Step 1: Start DFS at root (value 3). Path array is empty — no ancestors yet.

Step 2: Check root: scan path for max ancestor. Path is empty, so there are no ancestors with a greater value. Root 3 is always GOOD. Count = 1. Add 3 to path → path = [3].

Step 3: Move to left child (value 1). Path = [3, 1] (but we check before adding self). Scan path: max ancestor = 3.

Step 4: Check node 1: Is 1 ≥ 3? No. Node 1 is NOT good. Count stays 1. Add 1 to path → path = [3, 1].

Step 5: Move to left-left child (value 3). Scan path: max ancestor = max(3, 1) = 3.

Step 6: Check node 3: Is 3 ≥ 3? Yes! Node 3 is GOOD. Count = 2. Leaf node — backtrack. Remove values from path.

Step 7: Backtrack to root. Move to right child (value 4). Path = [3]. Scan: max ancestor = 3.

Step 8: Check node 4: Is 4 ≥ 3? Yes! Node 4 is GOOD. Count = 3. Add 4 to path → path = [3, 4].

Step 9: Move to left child of 4 (value 1). Path = [3, 4]. Scan: max ancestor = max(3, 4) = 4.

Step 10: Check node 1: Is 1 ≥ 4? No. NOT good. Count stays 3. Leaf — backtrack.

Step 11: Move to right child of 4 (value 5). Path = [3, 4]. Scan: max ancestor = 4.

Step 12: Check node 5: Is 5 ≥ 4? Yes! Node 5 is GOOD. Count = 4. Leaf — backtrack.

Step 13: DFS complete. All 6 nodes visited. Result = 4 good nodes.

Notice that at every node we scanned the full path to find the maximum — that is the redundant work this approach performs.

Brute Force — Full Path Scanning at Each Node — Watch how we maintain the entire root-to-node path and scan it at each node to determine if the node is good.

Algorithm

  1. Initialize a counter count = 0 and an empty list path.
  2. Perform DFS starting at the root:
    a. If the current node is null, return.
    b. Scan the entire path list to find the maximum ancestor value.
    c. If the current node's value ≥ the maximum ancestor value, increment count.
    d. Append the current node's value to path.
    e. Recurse on the left child, then the right child.
    f. Remove the last element from path (backtrack).
  3. Return count.

Code

class Solution {
public:
    int goodNodes(TreeNode* root) {
        int count = 0;
        vector<int> path;
        dfs(root, path, count);
        return count;
    }

    void dfs(TreeNode* node, vector<int>& path, int& count) {
        if (!node) return;

        // Scan entire path to find max ancestor
        int maxOnPath = INT_MIN;
        for (int val : path) {
            maxOnPath = max(maxOnPath, val);
        }

        if (node->val >= maxOnPath) {
            count++;
        }

        path.push_back(node->val);
        dfs(node->left, path, count);
        dfs(node->right, path, count);
        path.pop_back();
    }
};
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        count = 0

        def dfs(node, path):
            nonlocal count
            if not node:
                return

            # Scan entire path to find max ancestor
            max_on_path = max(path) if path else float('-inf')

            if node.val >= max_on_path:
                count += 1

            path.append(node.val)
            dfs(node.left, path)
            dfs(node.right, path)
            path.pop()

        dfs(root, [])
        return count
class Solution {
    private int count = 0;

    public int goodNodes(TreeNode root) {
        dfs(root, new ArrayList<>());
        return count;
    }

    private void dfs(TreeNode node, List<Integer> path) {
        if (node == null) return;

        // Scan entire path to find max ancestor
        int maxOnPath = Integer.MIN_VALUE;
        for (int val : path) {
            maxOnPath = Math.max(maxOnPath, val);
        }

        if (node.val >= maxOnPath) {
            count++;
        }

        path.add(node.val);
        dfs(node.left, path);
        dfs(node.right, path);
        path.remove(path.size() - 1);
    }
}

Complexity Analysis

Time Complexity: O(n × h)

We visit each of the n nodes exactly once. At every node, we scan the path list to find the maximum value, which takes O(h) time where h is the current depth (at most the tree height). Total work: O(n × h). In the worst case of a completely skewed tree (essentially a linked list), h = n, giving O(n²). For a balanced tree, h = log n, giving O(n log n).

Space Complexity: O(h)

The path list grows to at most h elements (the tree height). The recursion call stack also reaches depth h. In the worst case (skewed tree), this is O(n). In the best case (balanced tree), O(log n).

Why This Approach Is Not Efficient

The brute force approach scans the entire root-to-node path at every single node. With up to 10^5 nodes and a potentially skewed tree where the height equals n, the total work becomes O(n²) = 10^10 operations — far too slow for competitive programming time limits.

The fundamental waste is redundant recomputation. Consider a node and its child: the child's path is just the parent's path plus one more value. The maximum of the child's path is simply max(parent's path max, parent's value). We do not need to re-scan the entire list from scratch.

For example, if we know the maximum along the path [3, 1] is 3, then the maximum along the path [3, 1, 3] is just max(3, 3) = 3. There is no reason to iterate through the entire array again.

This insight — that the path maximum can be maintained incrementally with O(1) work per node instead of O(h) — leads directly to the optimal approach.

Optimal Approach - DFS with Maximum Tracking

Intuition

Instead of storing the full path and scanning it at every node, we can distill all the path information into a single number: the maximum value seen so far on the current root-to-node path.

Think of it like a high-score board in an arcade game. As you walk from the entrance (root) to a specific machine (node), every machine along the way has a posted score. You only need to remember the highest score you have seen — not every individual score. When you reach a new machine, you just compare its score against your remembered high score. If it matches or beats it, it qualifies.

In the DFS, we pass max_so_far as a parameter. At each node:

  • If node.val >= max_so_far, the node is good — increment count and update max_so_far to node.val.
  • If node.val < max_so_far, the node is not good — max_so_far stays the same.
  • Recurse on both children, passing the (possibly updated) max_so_far.

Because max_so_far is passed by value (or as a local copy), each branch of the tree naturally gets its own correct maximum. When we go left from a node, the left subtree sees one value of max_so_far. When we go right, the right subtree sees the same starting value — the branches do not interfere with each other.

Step-by-Step Explanation

Let's trace through the same Example 1 with the optimized approach.

Tree:

        3
       / \
      1   4
     /   / \
    3   1   5

Step 1: Start DFS at root (value 3). Initialize max_so_far to −∞ (a value below any node value) so the root is guaranteed to be counted.

Step 2: At root (3): 3 ≥ −∞ → GOOD. Count = 1. Update max_so_far = 3. Pass max_so_far = 3 to both children.

Step 3: Go left to child (value 1). max_so_far = 3 (inherited from root).

Step 4: At node 1: 1 < 3 → NOT good. Count stays 1. max_so_far stays 3. Continue to children.

Step 5: Go left to child (value 3). max_so_far = 3.

Step 6: At node 3: 3 ≥ 3 → GOOD (equal counts!). Count = 2. Leaf node — backtrack.

Step 7: Backtrack to root. Go right to child (value 4). Key: max_so_far resets to 3 (the value from the root), not 1. Each branch carries its own independent maximum.

Step 8: At node 4: 4 ≥ 3 → GOOD. Count = 3. Update max_so_far = 4 for this subtree.

Step 9: Go left to child (value 1). max_so_far = 4 (updated by parent node 4).

Step 10: At node 1: 1 < 4 → NOT good. The bar was raised by node 4. Count stays 3. Leaf — backtrack.

Step 11: Go right to child (value 5). max_so_far = 4.

Step 12: At node 5: 5 ≥ 4 → GOOD. Count = 4. Leaf — backtrack.

Step 13: DFS complete. Return 4. Each node did exactly one comparison — O(1) work per node, O(n) total.

Optimal DFS — Passing Maximum Along Each Path — Watch how we carry a single max_so_far value through the DFS, avoiding the need to scan the full path at every node.

Algorithm

  1. Define a recursive function dfs(node, maxSoFar) that returns the count of good nodes in the subtree rooted at node.
  2. Base case: If node is null, return 0.
  3. If node.val >= maxSoFar:
    • This node is good — set count = 1.
    • Update maxSoFar = node.val.
  4. Otherwise, set count = 0.
  5. Recurse: count += dfs(node.left, maxSoFar) + dfs(node.right, maxSoFar).
  6. Return count.
  7. Call dfs(root, −∞) from the main function. Using −∞ ensures the root is always counted.

Code

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, INT_MIN);
    }

    int dfs(TreeNode* node, int maxSoFar) {
        if (!node) return 0;

        int count = 0;
        if (node->val >= maxSoFar) {
            count = 1;
            maxSoFar = node->val;
        }

        count += dfs(node->left, maxSoFar);
        count += dfs(node->right, maxSoFar);
        return count;
    }
};
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_so_far):
            if not node:
                return 0

            count = 0
            if node.val >= max_so_far:
                count = 1
                max_so_far = node.val

            count += dfs(node.left, max_so_far)
            count += dfs(node.right, max_so_far)
            return count

        return dfs(root, float('-inf'))
class Solution {
    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;
            maxSoFar = node.val;
        }

        count += dfs(node.left, maxSoFar);
        count += dfs(node.right, maxSoFar);
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once. At every node, we perform a constant-time comparison (node value vs. max_so_far) and a constant-time update. No scanning of paths or lists — just O(1) work per node. Total: O(n).

Space Complexity: O(h)

The only extra space is the recursion call stack, which grows to the height h of the tree. For a balanced tree, h = O(log n). For a completely skewed tree (worst case), h = O(n). No additional data structures are needed — we replaced the entire path array with a single integer parameter.