Count Good Nodes in Binary Tree

Medium
1950.

Count Good Nodes in Binary Tree

Count Good Nodes in Binary Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.

Given the root of a binary tree, call a node good if no node on the path from the root down to it has a value larger than its own.

Return the number of good nodes in the tree.

Example 1

Input
root = [3,1,4,3,null,1,5]
Output
4
Explanation
The good nodes are the root 3, 4, 5 (above 3 and 4) and the left 3 (nothing above it is larger than 3).

Example 2

Input
root = [3,3,null,4,2]
Output
3
Explanation
3, its child 3 and 4 are good; 2 has the larger 3 above it.

Example 3

Input
root = [1]
Output
1
Explanation
The root is always good.

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= Node.val <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var goodNodes = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Good Nodes in Binary Tree — Problem & Solution

Count Good Nodes in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Good Nodes in Binary Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

Given the root of a binary tree, call a node good if no node on the path from the root down to it has a value larger than its own.

Return the number of good nodes in the tree.

Example 1

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: The good nodes are the root 3, 4, 5 (above 3 and 4) and the left 3 (nothing above it is larger than 3).

Example 2

Input: root = [3,3,null,4,2]
Output: 3
Explanation: 3, its child 3 and 4 are good; 2 has the larger 3 above it.

Example 3

Input: root = [1]
Output: 1
Explanation: The root is always good.

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= Node.val <= 10^4

Hints for Count Good Nodes in Binary Tree

  1. Hint 1

    A node is good exactly when its value is at least the maximum of all values above it.

  2. Hint 2

    So walk down the tree carrying the largest value seen on the current path.

  3. Hint 3

    Count the node if its value is at least that maximum, then pass max(maximum, node.val) to its children.

How to solve Count Good Nodes in Binary Tree

Carry the maximum value of the path from the root during a depth-first walk; a node is good when it is not smaller than that maximum.

Approach

  1. Call walk(root, root.val).
  2. At a node: it is good if node.val >= maxSoFar; set maxSoFar = max(maxSoFar, node.val).
  3. Return 1 (if good) plus the counts from both children with the updated maximum.

Why it works

The path from the root to a node is the path to its parent plus the node itself, so the maximum above a child is the parent's maximum updated with the parent's value — exactly what is passed down. Comparing against it checks the definition directly.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Equal values do not break goodness: compare with >=.
  • Starting the maximum at 0 is wrong when values are negative — start with the root's value.

Reference solution

Python

from typing import Optional

def goodNodes(root: Optional[TreeNode]) -> int:
    def walk(node, top):
        if node is None:
            return 0
        good = 1 if node.val >= top else 0
        top = max(top, node.val)
        return good + walk(node.left, top) + walk(node.right, top)

    return walk(root, root.val)

Java

public static int goodNodes(TreeNode root) {
    return goodWalk(root, root.val);
}

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

C++

int goodWalk(TreeNode* node, int top);

int goodNodes(TreeNode* root) {
    return goodWalk(root, root->val);
}

int goodWalk(TreeNode* node, int top) {
    if (!node) return 0;
    int good = node->val >= top ? 1 : 0;
    top = max(top, node->val);
    return good + goodWalk(node->left, top) + goodWalk(node->right, top);
}

JavaScript

var goodNodes = function(root) {
    return goodWalk(root, root.val);
};

var goodWalk = function(node, top) {
    if (node === null) return 0;
    var good = node.val >= top ? 1 : 0;
    top = Math.max(top, node.val);
    return good + goodWalk(node.left, top) + goodWalk(node.right, top);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)