Count Good Nodes in Binary Tree - Practice Coding Problems

Count Good Nodes in Binary Tree - Problem

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Input & Output

Example 1 — Standard Binary Tree

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

› Output: 4

💡 Note: Good nodes are: 3 (root, no ancestors), 4 (path: 3→4, max=3, 4≥3), left leaf 3 (path: 3→1→3, max=3, 3≥3), and 5 (path: 3→4→5, max=4, 5≥4). Total = 4 good nodes.

Example 2 — All Values Same

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

› Output: 3

💡 Note: Good nodes are: 3 (root), left 3 (path: 3→3, max=3, 3≥3), and 4 (path: 3→3→4, max=3, 4≥3). Node 2 is not good since path 3→3→2 has max=3 and 2<3.

Example 3 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: Only the root node exists. Root is always good since it has no ancestors to compare against.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes having different values

Check Paths

For each node, compare with maximum value on path from root

Count Good

Count nodes where value >= path maximum

Key Takeaway

🎯 Key Insight: Track maximum value from root to current node during DFS - a node is good if its value is at least this maximum

Asked in

a Amazon 45 M Microsoft 32 G Google 28 f Facebook 25

The key insight is to track the maximum value from root to current node during DFS traversal. A node is good if its value is greater than or equal to this path maximum. Best approach is DFS with path maximum tracking. Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Each Path	O(n²)	O(h)	For each node, trace path back to root and check if any ancestor is greater
DFS with Path Maximum	O(n)	O(h)	Single DFS traversal tracking maximum value from root to current node

Brute Force - Check Each Path — Algorithm Steps

Step 1: For each node in the tree
Step 2: Find path from root to current node
Step 3: Check if current node value >= all ancestors

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Node

Pick a node to check if it's good

Find Path

Trace path from root to current node

Compare

Check if node value >= all ancestors on path

Code -

solution.c — C

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* newNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int findPath(struct TreeNode* node, struct TreeNode* target, int* path, int* pathLen) {
    if (!node) return 0;
    path[(*pathLen)++] = node->val;
    if (node == target) return 1;
    if (findPath(node->left, target, path, pathLen) || findPath(node->right, target, path, pathLen)) {
        return 1;
    }
    (*pathLen)--;
    return 0;
}

int isGoodNode(struct TreeNode* root, struct TreeNode* node) {
    int path[1000];
    int pathLen = 0;
    findPath(root, node, path, &pathLen);
    if (pathLen == 1) return 1;
    int maxVal = INT_MIN;
    for (int i = 0; i < pathLen - 1; i++) {
        if (path[i] > maxVal) maxVal = path[i];
    }
    return node->val >= maxVal;
}

int countNodes(struct TreeNode* node, struct TreeNode* root) {
    if (!node) return 0;
    int count = isGoodNode(root, node) ? 1 : 0;
    count += countNodes(node->left, root);
    count += countNodes(node->right, root);
    return count;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    return countNodes(root, root);
}

int main() {
    // Simple test with hardcoded tree [3,1,4,3,null,1,5]
    struct TreeNode* 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", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially traverse path of length h, giving O(n×h) where h can be n

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Path — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler