Given a binary tree containing N nodes, where each node contains some value. Count the number of good nodes in the tree.

## Count Good Nodes In Binary Tree Video Explanation

## Count Good Nodes In Binary Tree Solution

A node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

For example, in the below tree

The nodes marked in blue are good nodes, because they satisfy the definition of good node given above. Therefore, for the tree given above, the output will be 4.

## Solution

We can easily count the number of good nodes in a tree by iterating through the tree recursively and maintaining the maximum number seen so far in a variable called `maxSoFar`

.

While visiting any node `X`

, if the `maxSoFar < X`

, then we increment the `count`

. We keep on doing that until we have visited every node and finally print the count.

## Solution Implementation

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int goodNodes(TreeNode* root) { int count = 0; dfs(root, root->val, count); return count; } void dfs(TreeNode* root, int maxSoFar, int& count) { if( root == NULL) { return; } if (maxSoFar <= root->val) { count++; } dfs(root->left, max(maxSoFar, root->val), count); dfs(root->right, max(maxSoFar, root->val), count); } };