2265. Count Nodes Equal To Average of Subtree

Leetcode

📝 Problem Details

• Title: 2265. Count Nodes Equal To Average of Subtree
• Link: https://leetcode.com/problems/count-nodes-equal-to-average-of-subtree/
• Difficulty: Medium
• Tags/Categories: Trees Recursion Traversal Postorder

💭What Were My Initial Thoughts?

- we need a way of traversing the tree
- throughout this traversal we need to track and compare the value of a node and the average of its subtree
- we also need a counter that can be maintained throughout traversal for the number of nodes that meet our criteria

🤔What Did I Struggle With?

- how to implement a recursive solution that can keep track of our above criteria
	- was not thinking about passing our results by reference recursively
- i was using the incorrect traversal method
- i was trying to make an in-order traversal method work in a case where it wasn't appropriate

💡 Explanation of Solution

1. Postorder Traversal: Recursively process left and right subtrees before the current node

2. Subtree Calculation: Compute the sum and count of nodes for each subtree

3. Condition Check: Compare the node's value to the average of its subtree and update the count if they match

⌛ Complexity Analysis

Time Complexity: O(n)
- bound by the traversal of each node in the tree
- calculation of the sum, averages, and total number of nodes that abide by the condition is done in O(1) time

Space Complexity: O(n) or O(log n) depending on the balancing factor of the tree

💻 Implementation of Solution

class Solution {
public:
	pair<int, int> calculateSubtree(TreeNode* root, int& result) {
		if(root == nullptr) return {0, 0}; // Base Case
 
		// Recur for left and right subtrees
		auto left = calculateSubtree(root->left, result);
		auto right = calculateSubtree(root->right, result);
		// Current subtree sum and count
		int subtreeSum = left.first + right.first + root->val;
		int subtreeCount = left.second + right.second + 1;
 
        // Check if the root value equals the average of the subtree
		if(root->val == subtreeSum / subtreeCount) {
			result++;
		}
 
		return {subtreeSum, subtreeCount};
	}
	
	int averageOfSubtree(TreeNode* root) {
		int result = 0; // Count of nodes matching the condition
		calculateSubtree(root, result);
		return result;
	}
}