Count Good Nodes in Binary Tree

This question sounds strange at first. What makes a node “good”? Once you know the rule, the problem becomes a clean tree walk. The interviewer wants to see if you can carry a small piece of information down the tree as you go. That skill shows up in many tree problems.

🎯 The Problem

You get the root of a binary tree and must count how many nodes are good.

The rules:

• A binary tree is a structure where each node has at most two children.
• A node is good if no node on the path from the root down to it has a larger value.
• In plain words, a node is good when it is at least as big as everything above it on its path.
• The root is always good, because nothing sits above it.

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

        3
      /   \
     1     4
    /     /  \
   3     1    5

Explanation: Good nodes are 3 (root), 3, 4, and 5.

Walk the paths. The root 3 is good. Going left, 1 is smaller than 3, so it is not good. Below it 3 equals the max so far, so it is good. Going right, 4 is bigger than 3, so it is good. Below 4, the 1 is smaller, so not good. The 5 is bigger than 4, so it is good. That is four good nodes.

Here is the tree so you can trace each path yourself.

🐢 Approach 1: Recheck the Path Per Node (Brute Force)

The idea in one line: for every node, redo the path from the root and check if anything on it is bigger.

The idea:

• Follow the definition word for word.
• For each node, look at every node on its path from the root.
• If none of them is bigger, the node is good.

How it works:

• A node usually has no link back to its parent.
• So for each node you walk a fresh path from the top.
• Count the node as good only if no value on that path beats it.

Why it is weak:

• The path from the root to a deep node is walked over and over for every node below it.
• The deeper the tree, the longer each repeated path.
• This climbs toward O(n²) time.

Here is the carry-path-maximum code:

def good_nodes(root):
    def dfs(node, best):
        if not node: return 0
        good = 1 if node.val >= best else 0
        best = max(best, node.val)
        return good + dfs(node.left, best) + dfs(node.right, best)
    return dfs(root, float("-inf"))

⚡ Approach 2: DFS Carrying the Max So Far (Best)

The idea in one line: walk down once and carry the biggest value seen on the path so far.

The idea:

• The running max is the largest value from the root down to where you are.
• A node is good when it is at least as big as the running max.
• Why? The running max already holds the biggest thing above it, so nothing above is bigger.

How it works:

• Use DFS, short for depth-first search, which goes deep into one branch before trying the next.
• At each node, compare its value with the running max passed in.
• Update the running max to the larger of the old max and this node’s value.
• Pass that new max down to both children.

Why it is fast:

• Each node is visited once. You never redo a path.
• The running max travels down with you and does all the checking.
• That gives a clean O(n) pass.

This diagram shows the running max flowing down each path and which nodes turn out good.

Steps to Solve

1. Start at the root with the running max set to the root’s value, or a very small number.
2. At each node, compare its value with the running max passed in.
3. If the node value is at least the running max, count it as good.
4. Update the running max to the larger of the old max and the current node value.
5. Walk into the left child with the updated max, then the right child with the updated max.
6. Add up the good counts from this node and both subtrees.
7. Return the total.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int countGood(Node* node, int maxSoFar) {
    if (node == NULL) return 0;
    int count = 0;
    if (node->val >= maxSoFar) {        // at least as big as everything above
        count = 1;
    }
    int newMax = node->val > maxSoFar ? node->val : maxSoFar;
    count += countGood(node->left, newMax);
    count += countGood(node->right, newMax);
    return count;
}

int main(void) {
    Node* root = newNode(3);
    root->left = newNode(1);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->right->left = newNode(1);
    root->right->right = newNode(5);

    printf("%d\n", countGood(root, INT_MIN));
    return 0;
}

4

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int countGood(Node* node, int maxSoFar) {
    if (!node) return 0;
    int count = (node->val >= maxSoFar) ? 1 : 0;  // good check
    int newMax = max(maxSoFar, node->val);
    count += countGood(node->left, newMax);
    count += countGood(node->right, newMax);
    return count;
}

int main() {
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(4);
    root->left->left = new Node(3);
    root->right->left = new Node(1);
    root->right->right = new Node(5);

    cout << countGood(root, INT_MIN) << endl;
    return 0;
}

4

public class CountGoodNodes {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    public static int countGood(Node node, int maxSoFar) {
        if (node == null) return 0;
        int count = (node.val >= maxSoFar) ? 1 : 0;   // good check
        int newMax = Math.max(maxSoFar, node.val);
        count += countGood(node.left, newMax);
        count += countGood(node.right, newMax);
        return count;
    }

    public static void main(String[] args) {
        Node root = new Node(3);
        root.left = new Node(1);
        root.right = new Node(4);
        root.left.left = new Node(3);
        root.right.left = new Node(1);
        root.right.right = new Node(5);

        System.out.println(countGood(root, Integer.MIN_VALUE));
    }
}

4

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def count_good(node, max_so_far):
    if node is None:
        return 0
    count = 1 if node.val >= max_so_far else 0   # good check
    new_max = max(max_so_far, node.val)
    count += count_good(node.left, new_max)
    count += count_good(node.right, new_max)
    return count


root = Node(3)
root.left = Node(1)
root.right = Node(4)
root.left.left = Node(3)
root.right.left = Node(1)
root.right.right = Node(5)

print(count_good(root, float("-inf")))

4

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function countGood(node, maxSoFar) {
  if (node === null) return 0;
  let count = node.val >= maxSoFar ? 1 : 0;   // good check
  const newMax = Math.max(maxSoFar, node.val);
  count += countGood(node.left, newMax);
  count += countGood(node.right, newMax);
  return count;
}

const root = new Node(3);
root.left = new Node(1);
root.right = new Node(4);
root.left.left = new Node(3);
root.right.left = new Node(1);
root.right.right = new Node(5);

console.log(countGood(root, -Infinity));

4

Let us walk through the Python version line by line.

The function starts with if node is None: return 0. When we run off the bottom of the tree there is no node. An empty spot has no good nodes. So we return zero and stop that branch.

The line count = 1 if node.val >= max_so_far else 0 does the good check. The max_so_far is the biggest value on the path above this node. If our node is at least as big, nothing above beats it, so it is good and we count one. If it is smaller, it is not good and we count zero.

Then new_max = max(max_so_far, node.val) updates the running max. We take the larger of the old max and this node’s value. This new max is what the children should compare against, because now this node is part of their path above.

The next two lines recurse into the children. count += count_good(node.left, new_max) and the same for the right child. We pass the updated max down. Each call returns the good count for that whole subtree, and we add both to our own count.

Finally return count hands back the total good nodes for this node and everything under it. We start the whole thing with float("-inf"), a value smaller than any real number. So the root always passes the good check, which matches the rule that the root is always good.

⏱️ Time and Space Complexity

The DFS visits every node once and does a tiny bit of work at each. So it is O(n) in time where n is the number of nodes. The brute force redoes the path from the root for each node, so in the worst case it can climb toward O(n²). For space, the DFS uses the call stack, which goes as deep as the tree. So the space is O(h), where h is the height of the tree. The big idea is that carrying the running max turns repeated path work into a single clean pass.

🧩 Key Takeaways

• ✅ A node is good when it is at least as big as every node above it on its path.
• ✅ Carry the running max down the tree so each node can check itself instantly.
• ✅ The root is always good, so start the max at a very small number.
• ✅ One DFS pass visits each node once, giving O(n) time.
• ✅ The same carry-a-value-down idea solves many other tree problems.

🚀 What’s Next?

• Binary Tree Right Side View
• Maximum Depth of Binary Tree