Count Good Nodes in Binary Tree — Medium Coding Interview Question

Given a binary tree root, a node X is 'good' if in the path from the root to X, there is no node with a value greater than X's value. Return the number of good nodes.

Example

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

Output: 4

Constraints

• The number of nodes is in the range [1, 10⁵]
• -10⁴ ≤ Node.val ≤ 10⁴

Topics & Companies

Topics: trees

Asked by: Amazon, Microsoft

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(h).

Practice more

• All DSA Problems
• DSA Patterns