Count Good Nodes in Binary Tree

Medium

Problem

A node is good if no node on the path from the root to it has a greater value. Return the number of good nodes.

Example 1

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

Nodes 3 (root), 4, 5 and the lower 3.

Test cases

Case 1

Input:    [3,1,4,3,null,1,5]
Expected: 4

Case 2

Input:    [3,3,null,4,2]
Expected: 3

Case 3

Input:    [1]
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DFS carrying the path maximum

Time O(n)Space O(h)

A node is good if its value ≥ the maximum seen from the root to it.

function goodNodes(root) {
const dfs = (node, max) => {
if (!node) return 0;
const good = node.val >= max ? 1 : 0;
max = Math.max(max, node.val);
return good + dfs(node.left, max) + dfs(node.right, max);
};
return dfs(root, -Infinity);
}