Count Good Nodes in Binary Tree
mediumTrees & BST II+20 XPTime limit 2s
Walk from the root down to some node x. Call x good if no node on that walk (including the root) has a value greater than x's value — x is at least as large as everything above it. How many good nodes does the tree have?
Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is
3
/ \
9 20
/ \
15 7
Input: one tree.
Output: the number of good nodes (0 for an empty tree). The root is always good.
Constraints: 0 ≤ nodes ≤ 10⁴, −1000 ≤ value ≤ 1000. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.
Think about it: carry the largest value seen so far on the way down (DFS). A node is good when its value is at least that maximum; then pass max(maxSoFar, node.val) to its children.
Sample input 1
3 1 4 3 null 1 5
Sample output 1
4
Sample input 2
3 3 null 4 2
Sample output 2
3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).