🚀 100% || DFS || Explained Intuition🚀
Problem Description\n\nGiven the root of a binary tree. The task is to determine the number of nodes in the tree whose value matches the floored average of all 
# Problem Description\n\nGiven the **root** of a binary tree. The task is to determine the **number** of nodes in the tree whose value **matches** the floored **average** of all the values within their respective **subtrees**. In other words, you need to count the nodes where the node\'s value is equal to the integer average of all values in its subtree.\n\n- Here\'s some additional information to keep in mind:\n\n    - The **average** of a set of elements is calculated by **summing** those elements and **dividing** the sum by the **number** of elements.\n    - A **subtree** of a given node **includes** the node **itself** and all of its **descendant** nodes.\n\nThe **goal** is to find the count of nodes in the binary tree that **meet** this condition.\n\n- **Constraints:**\n    - The number of nodes in the tree is in the range `[1, 1000]`.\n    - `0 <= Node.val <= 1000`.\n    \n---\n\n\n# Intuition\n\nHello there,\uD83D\uDE04\n\nLet\'s look\uD83D\uDC40 at today\'s problem.\nIn today\'s problem, We have a **tree**\uD83C\uDF32 and each node in it have a value and for each node we have to check if its value is **equal** to the average of values in its **subtree**. If so, calculate number of nodes with this description.\uD83E\uDD28\n\nBut before that what is a **subtree** of a node ?\uD83E\uDD14\nA subtree in general is a part of a tree\uD83C\uDF32 but for a specific node the subtree is the part of the tree that containing all of its children and descnedants going down to the **leaves**.\uD83C\uDF43\nlet\'s see an example.\n![image.png](https://assets.leetcode.com/users/images/972ea752-680c-4104-a65f-1fd45e8ceb9f_1698892997.850533.png)\n\nHere the subtree of `node 2` is the part with **blue** color. the subtree of `node 3` is the part with **red** color and also we can consider the **whole tree** as a subtree for `node 1`.\n\nNow how we get the values and number of nodes for all of the node subtree?\uD83E\uDD14\nI will pretend that I didn\'t say the algorithm in the title.\uD83D\uDE02\nWe can do it with a simple algorithm that **traverses** the tree and there is no simpler tha **DFS**, Our hero today\uD83E\uDDB8\u200D\u2642\uFE0F.\n\n- And since any **tree**:\n    - has only **one** **root**.\n    - **doesn\'t** have **loops**.\n    \nThen we can apply **DFS** at the only **root** of the tree and without concerning about the loops.\nThe **DFS** Function of any node will **check** for all nodes in its subtree that meet our requirements and return the number of nodes in its subtree and the sum of values for its subtree.\uD83D\uDCAA\n\n![image.png](https://assets.leetcode.com/users/images/294d9ee8-1618-4e96-ad75-6d74319addb6_1698893761.4867618.png)\nThis is an example how our DFS will look like for each node since it will return `(sum of values of subtree, number of nodes)`.\n\nAnd this is the solution for our today\'S problem I hope that you understood it\uD83D\uDE80\uD83D\uDE80\n\n\n\n\n---\n\n\n\n# Approach\n1. Initialize an integer variable `matchingSubtreeCount` to keep track of subtrees with matching averages.\n2. Create a Depth-First Search **DFS** function `calculateSubtreeValues` that takes a `currentNode` as input and returns a pair of integers. These integers represent:\n   - The **sum** of values within the current subtree.\n   - The **number** of nodes within the current subtree.\n3. In the `calculateSubtreeValues` function:\n    - **Base Case**: check if the `currentNode` is null. If it is, return `{0, 0}`, signifying that both the sum and number of nodes are zero for a null node.\n    - The **sum** of values in the current subtree is the **sum** of values in the left and right subtrees **plus** the value of the `currentNode` and The **number** of nodes is **number** of nodes in the left and right subtrees then **increment** it by 1 for the `currentNode`.\n    - **Increment** the `matchingSubtreeCount` if the current node\'s value matches the average of its subtree.\n    - **Return** a pair of values `{sumOfValues, numberOfNodes}` representing the calculated values for the current subtree.\n11. In the main function, perform **DFS** from the root then return `matchingSubtreeCount` after traversing over all the nodes.\n\n\n# Complexity\n- **Time complexity:**$O(N)$\nSince the DFS **traverse** over all the nodes of the tree then the complexity is `O(N)` where `N` is the number of nodes within the tree.\n- **Space complexity:**$O(N)$\nSince the DFS is a **recursive** call and it reserves a **memory stack frame** for each call so the **maximum** number of calls it can make in the same time is `N` calls so complexity is `O(N)`;\n\n\n---\n\n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int matchingSubtreeCount = 0; // Initialize the count of subtrees with matching averages.\n\n    // A Depth-First Search (DFS) function and returns a pair of values:\n    // - The sum of values within the current subtree.\n    // - The number of nodes within the current subtree.\n    pair<int, int> calculateSubtreeValues(TreeNode* currentNode) {\n        if (currentNode == nullptr)\n            return {0, 0}; // Base case: Return 0 for both sum and number of nodes if the node is null.\n\n        // Recursively calculate values for the left and right subtrees.\n        auto leftSubtree = calculateSubtreeValues(currentNode->left);\n        auto rightSubtree = calculateSubtreeValues(currentNode->right);\n\n        // Calculate the sum of values and the number of nodes in the current subtree.\n        int sumOfValues = leftSubtree.first + rightSubtree.first + currentNode->val;\n        int numberOfNodes = leftSubtree.second + rightSubtree.second + 1;\n\n        // Check if the current node\'s value matches the average of its subtree.\n        if (sumOfValues / numberOfNodes == currentNode->val)\n            matchingSubtreeCount++; \n\n        return {sumOfValues, numberOfNodes}; // Return the calculated values for the current subtree.\n    }\n\n    int averageOfSubtree(TreeNode* root) {\n        calculateSubtreeValues(root); // Start the DFS from the root node.\n        return matchingSubtreeCount; \n    }\n};\n```\n```Java []\nclass Solution {\n    private int matchingSubtreeCount = 0; // Initialize the count of subtrees with matching averages.\n\n    // A Depth-First Search (DFS) function that returns an array of two values:\n    // - The sum of values within the current subtree.\n    // - The number of nodes within the current subtree.\n    private int[] calculateSubtreeValues(TreeNode currentNode) {\n        if (currentNode == null)\n            return new int[]{0, 0}; // Base case: Return 0 for both sum and number of nodes if the node is null.\n\n        // Recursively calculate values for the left and right subtrees.\n        int[] leftSubtree = calculateSubtreeValues(currentNode.left);\n        int[] rightSubtree = calculateSubtreeValues(currentNode.right);\n\n        // Calculate the sum of values and the number of nodes in the current subtree.\n        int sumOfValues = leftSubtree[0] + rightSubtree[0] + currentNode.val;\n        int numberOfNodes = leftSubtree[1] + rightSubtree[1] + 1;\n\n        // Check if the current node\'s value matches the average of its subtree.\n        if (sumOfValues / numberOfNodes == currentNode.val)\n            matchingSubtreeCount++;\n\n        return new int[]{sumOfValues, numberOfNodes}; // Return the calculated values for the current subtree.\n    }\n\n    public int averageOfSubtree(TreeNode root) {\n        calculateSubtreeValues(root); // Start the DFS from the root node.\n        return matchingSubtreeCount; \n    }\n}\n```\n```Python []\nclass Solution:\n    def __init__(self):\n        self.matchingSubtreeCount = 0  # Initialize the count of subtrees with matching averages.\n\n    # A Depth-First Search (DFS) function that returns a tuple of two values:\n    # - The sum of values within the current subtree.\n    # - The number of nodes within the current subtree.\n    def calculateSubtreeValues(self, currentNode):\n        if currentNode is None:\n            return 0, 0  # Base case: Return 0 for both sum and number of nodes if the node is None.\n\n        # Recursively calculate values for the left and right subtrees.\n        leftSubtree  = self.calculateSubtreeValues(currentNode.left)\n        rightSubtree = self.calculateSubtreeValues(currentNode.right)\n\n        # Calculate the sum of values and the number of nodes in the current subtree.\n        sumOfValues  = leftSubtree [0] + rightSubtree[0] + currentNode.val\n        numberOfNodes  = leftSubtree [1] + rightSubtree[1] + 1\n\n        # Check if the current node\'s value matches the average of its subtree.\n        if sumOfValues  // numberOfNodes  == currentNode.val:\n            self.matchingSubtreeCount += 1\n\n        return sumOfValues , numberOfNodes   # Return the calculated values for the current subtree.\n\n\n    def averageOfSubtree(self, root):\n        self.calculateSubtreeValues(root)  # Start the DFS from the root node.\n        return self.matchingSubtreeCount \n\n```\n\n\n![HelpfulJerry.jpg](https://assets.leetcode.com/users/images/c51170b6-4369-4c7a-919b-9c0a840dba22_1698888487.897979.jpeg)\n
['Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3']