1448. Count Nodes in Binary Tree

📝 Problem Details

• Title: 1448. Count Nodes in Binary Tree
• Link: https://leetcode.com/problems/count-good-nodes-in-binary-tree/
• Difficulty: Medium
• Tags/Categories: Trees DFS

💭What Were My Initial Thoughts?

what is a "good" node?
- in the path from root to X, there are no nodes with value greater than X

- we need a way or tracking the maxValue node in a path encountered SO FAR as we recursively traverse the tree
- a helper function that takes in the max value as a paramter would be beneficial

💡 Explanation of Solution

- DFS preorder traversal
- helper function that takes in the root node and an integer for the maxVal encountered in the path so far
- check if the current node is a "good node" by comparing it against the maxSoFar
	- increment the count if it is a good node
- recursively append to count by calling the function on the left and right children
- return the count

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n) worst case

💻 Implementation of Solution

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return countGoodNodes(root, INT_MIN);
    }
 
    int countGoodNodes(TreeNode* node, int maxSoFar) {
        if(!node) return 0;
 
        int count = 0;
        if(node->val >= maxSoFar) {
            count = 1;
            maxSoFar = node->val;
        }
 
        count += countGoodNodes(node->left, maxSoFar);
        count += countGoodNodes(node->right, maxSoFar);
 
        return count;
    }
};