codejump
MediumPythonJavaScriptTypeScript

Binary Tree — Count Good Nodes

Data StructuresTreesRecursionDFS

In a binary tree, a node is good if no node on the path from the root to it
has a value greater than the node's own value. The root is always good.

solve(levelOrder) receives the tree serialized level by level and returns the
number of good nodes.

Examples

solve([3, 1, 4, 3, null, 1, 5])  → 4   // 3 (root), 4, 3 under the 1, and 5
solve([3, 3, null, 4, 2])        → 3   // 2 is below a 3 and a 3 and is smaller
solve([1])                       → 1
solve([])                        → 0

Equal values count: a node whose value ties with the current maximum is good.

Sample tests

Test #1Classic example
Input: [[3,1,4,3,null,1,5]]
Output: 4
Test #2Ties with the maximum count as good
Input: [[3,3,null,4,2]]
Output: 3
Test #3The root is always good
Input: [[1]]
Output: 1