Tree Binary Tree Binary Search Tree Breadth First Search Depth First Search
Intermediate Level

Implement the countGoodNodesBinaryTree method that counts good nodes in a binary tree.

You are given binary tree values in level-order array form, where 0 represents a missing node. A node is called good if no node on the path from the root to that node has a value greater than it.

Return the number of good nodes in the tree.

Example 1
Input:
tree (int[]) = [3,1,4,3,0,1,5]
size (int) = 7
Return:
(int) 4
Example 2
Input:
tree (int[]) = [3,3,0,4,2]
size (int) = 5
Return:
(int) 3
Example 3
Input:
tree (int[]) = [1]
size (int) = 1
Return:
(int) 1

Use depth-first search while carrying the maximum value seen on the current root-to-node path.

When visiting a node, compare its value with the path maximum. If the node value is greater than or equal to the maximum, it is a good node. Then update the maximum and continue to its children.

Every node is checked once.

Pseudocode:

function countGoodNodesBinaryTree(tree, size):
    function dfs(index, maxSoFar):
        if index is invalid or tree[index] is 0:
            return 0
        count = 0
        if tree[index] >= maxSoFar:
            count = 1
        newMax = max(maxSoFar, tree[index])
        count += dfs(left child index, newMax)
        count += dfs(right child index, newMax)
        return count
    return dfs(0, negative infinity)
Run your code to see the result.