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) =
7Returns (int)
4Example 2
Input
tree (int[]) =
[3,3,0,4,2]size (int) =
5Returns (int)
3Example 3
Input
tree (int[]) =
[1]size (int) =
1Returns (int)
1Use 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)Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run