✅ Easiest Possible Approach with Video Explanation✅ Beats 100% ✅ Fastest Too
\n\n\n# YouTube Video Explanation:\n\nhttps://youtu.be/XGFLJ7HWSPE\n\n\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making
![Screenshot 2023-11-02 104747.png](https://assets.leetcode.com/users/images/80fcf130-e49f-40d4-8bb6-4cec72b6597a_1698902927.4267428.png)\n\n\n# YouTube Video Explanation:\n\n[https://youtu.be/XGFLJ7HWSPE](https://youtu.be/XGFLJ7HWSPE)\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 200 Subscribers*\n*Current Subscribers: 172*\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to count the number of nodes in a binary tree where the value of the node is equal to the average of the values in its subtree. We need to traverse the tree and keep track of the sum and count of values in the subtree to calculate the average.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. We perform a Depth-First Search (DFS) traversal of the binary tree.\n2. For each node, we recursively calculate the sum and count of values in its left and right subtrees.\n3. We then compute the sum and count of values in the current subtree (including the current node).\n4. If the current node\'s value is equal to the computed average, we increment the result.\n5. We return the sum and count of the current subtree to the parent node.\n\n# Complexity\n- Time Complexity: O(N) - We visit each node once during the DFS traversal.\n- Space Complexity: O(H) - In the worst case, the space complexity is O(H), where H is the height of the binary tree, due to the recursion stack.\n\n# Code\n## Java\n```\nclass Solution {\n    int result = 0;\n\n    public int averageOfSubtree(TreeNode root) {\n        dfs(root);\n        return result;\n    }\n\n    private int[] dfs(TreeNode node) {\n        if (node == null) {\n            return new int[]{0, 0};\n        }\n\n        int[] left = dfs(node.left);\n        int[] right = dfs(node.right);\n\n        int currentSum = left[0] + right[0] + node.val;\n        int currentCount = left[1] + right[1] + 1;\n\n        if (currentSum / currentCount == node.val) {\n            result++;\n        }\n\n        return new int[]{currentSum, currentCount};\n    }\n}\n```\n## C++\n```\nclass Solution {\npublic:\n    int result = 0;\n\n    int averageOfSubtree(TreeNode* root) {\n        dfs(root);\n        return result;\n    }\n\n    vector<int> dfs(TreeNode* node) {\n        if (!node) {\n            return {0, 0};\n        }\n\n        vector<int> left = dfs(node->left);\n        vector<int> right = dfs(node->right);\n\n        int currentSum = left[0] + right[0] + node->val;\n        int currentCount = left[1] + right[1] + 1;\n\n        if (currentSum / currentCount == node->val) {\n            result++;\n        }\n\n        return {currentSum, currentCount};\n    }\n};\n```\n## Python\n```\nclass Solution(object):\n    def __init__(self):\n        self.result = 0\n\n    def averageOfSubtree(self, root):\n        self.dfs(root)\n        return self.result\n\n    def dfs(self, node):\n        if not node:\n            return [0, 0]\n\n        left = self.dfs(node.left)\n        right = self.dfs(node.right)\n\n        currentSum = left[0] + right[0] + node.val\n        currentCount = left[1] + right[1] + 1\n\n        if currentSum // currentCount == node.val:\n            self.result += 1\n\n        return [currentSum, currentCount]\n        \n```\n## JavaScript\n```\nvar averageOfSubtree = function(root) {\n    let result = 0;\n\n    const dfs = (node) => {\n        if (!node) {\n            return [0, 0];\n        }\n\n        const left = dfs(node.left);\n        const right = dfs(node.right);\n\n        const currentSum = left[0] + right[0] + node.val;\n        const currentCount = left[1] + right[1] + 1;\n\n        if (Math.floor(currentSum / currentCount) === node.val) {\n            result++;\n        }\n\n        return [currentSum, currentCount];\n    };\n\n    dfs(root);\n    return result;\n};\n```\n![upvote1.jpeg](https://assets.leetcode.com/users/images/a4773560-76df-493c-8489-d92ed145ffe6_1698902771.5412507.jpeg)\n\n\n\n\n\n\n
['Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'C++', 'Java', 'JavaScript']