Count Good Nodes In Binary Tree | LeetCode

Problem Source

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);
    }
};