Count Good Nodes In Binary Tree

Medium · Trees

You are given the root of a binary tree where each node has an integer value. A node is called good if, along the path from the root down to that node, no earlier node has a strictly greater value than it (the node itself counts as being compared against everything above it, including the root). Return the total number of good nodes in the tree.

Examples

Input:  root = [3,1,4,3,null,1,5]
Output: 4
Why:    The path values from root to each node are checked; nodes 3(root), 3(left-left), 4, and 5 each have no ancestor with a strictly greater value, giving 4 good nodes.

Input:  root = [3,3,null,4,2]
Output: 3
Why:    Root 3, its child 4, and the second 3 are each at least as large as every value seen above them on their path.

Input:  root = [1]
Output: 1
Why:    A single node has no ancestors so it is trivially good.

Constraints

1 <= number of nodes <= 10^5, -10^4 <= node value <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Count Good Nodes In Binary Tree

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Count Good Nodes In Binary Tree. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.