【Video】Give me 8 minutes - How we think about a solution - Why we use postorder traversal?
Intuition\nCalculate subtree of left and right child frist\n\n---\n\n# Solution Video\n\nhttps://youtu.be/MV6NpUXCfUU\n\n\u25A0 Timeline of the video\n0:05 Whic
# Intuition\nCalculate subtree of left and right child frist\n\n---\n\n# Solution Video\n\nhttps://youtu.be/MV6NpUXCfUU\n\n\u25A0 Timeline of the video\n`0:05` Which traversal do you use for this question?\n`1:55` How do you calculate information you need?\n`3:34` How to write Inorder, Preorder, Postorder\n`4:16` Coding\n`7:50` Time Complexity and Space Complexity\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 2,919\nMy initial goal is 10,000\nThank you for your support!\n\n---\n\n# Approach\n\n### How we think about a solution.\n\nFirst of all, we know that we have to traverse the tree and have 3 well known traversal.\n\nTo be honest, I asked you about the same question in the yesterday\'s post. lol\n\n---\n\n\u25A0 Question\n\nWhich traversal do you use?\n\n---\n\nThinking time...\n\n... \uD83D\uDE29\n\n... \uD83D\uDE0F\n\n... \uD83D\uDE06\n\n... \uD83D\uDE04\n\nMy answer is postorder\n\n---\n\n\u2B50\uFE0F Points\n\nThe reason why we choose postorder traversal is that it processes child nodes (left and right subtrees) first to calculate the subtree\'s sum, number of nodes and number of results, then uses that information to check the condition at the parent node.\n\nTo calculate that information of a subtree including a parent, it is necessary to use information from the child nodes. That\'s why the left and right subtrees should be processed first.\n\nWhen we have\n```\n   5\n  /  \\\n 6    7\n\n```\n\nthe order of postorder process should be 6, 7 and 5.\n\nSo, we have information of subtree of 6 and information of subtree of 7, then finally we can calculate information of subtree of 5 which is including 6 and 7. \n\n---\n\n- How do you calculate information we need?\n\nTo get result, we need `total sum` and `total number of nodes` because we calculate average of each subtree. This is not complicated. just\n\n#####  Total Sum\n---\n`sum of left subtree` + `sum of right subtree` + `current value`\n\n---\n##### Number of nodes\n---\n\n\n`number of nodes from left` + `number of nodes from right` + 1\n\n`+1` is for a current node\n\n---\n\nEasy!\n\nThen every time we calculate number of results with this condition\n\n##### Number of results\n---\n\n\u2B50\uFE0F Points\n\nres += `(node.val == total_sum // total_count)`\n\n---\n\n---\n\n\u25A0 Python Tips\n\nAbout calculation of number of results\n\nIn Python, `True` is equivalent to the integer `1`, and `False` is equivalent to the integer `0`. This is based on implicit conversion between Python\'s boolean type (`bool`) and integer type (`int`). Here are some examples:\n\n```python []\nbool_true = True\nint_one = 1\n\nbool_false = False\nint_zero = 0\n\n# True and 1 are equivalent\nprint(bool_true == int_one)  # True\n\n# False and 0 are equivalent\nprint(bool_false == int_zero)  # True\n```\n\nAs a result, if a condition is `True`, it is considered as satisfied and is treated as the integer `1`. The result is then added to the variable `res`, which counts the number of nodes that meet the condition.\n\nThat is just pretentious coding style. lol\nIt\'s the same as\n\n```Python []\nres += (node.val == total_sum // total_count)\n\u2193\nif node.val == total_sum // total_count:\n    res += 1\n```\n\n---\n\n- How to write inorder, preorder, postorder\n\nAcutually, I wrote the same contents yesterday, but knowing how to write inorder, preorder, and postorder traversals might be helpful for other problems as well.\n\n```python []\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\ndef inorder(root):\n    if not root:\n        return []\n    result = []\n    result += inorder(root.left)\n    result.append(root.val)\n    result += inorder(root.right)\n    return result\n\ndef preorder(root):\n    if not root:\n        return []\n    result = []\n    result.append(root.val)\n    result += preorder(root.left)\n    result += preorder(root.right)\n    return result\n\ndef postorder(root):\n    if not root:\n        return []\n    result = []\n    result += postorder(root.left)\n    result += postorder(root.right)\n    result.append(root.val)\n    return result\n```\n\nLet\'s focus on `result.append(root.val)` in each function.\n\n---\n\n\u2B50\uFE0F Points\n\nFor `Inorder`, we do something `between left and right`.\nFor `Preorder`, we do something `before left and right`.\nFor `Postorder`, we do something `after left and right`.\n\n---\n\nWe use `postorder` this time, so do the key point above after left and right.\n\nYou can compare `postorder` with `inorder` by yesterday\'s daily coding challenge. I put yesterday\'s video and post at bottom of the post.\n\nLet\'s see a real algorithm!\n\n### Algorithm Overview:\n\nThe algorithm calculates the number of nodes in a binary tree where the value of the node is equal to the average value of its subtree. It uses a post-order traversal to process the tree nodes.\n\n### Detailed Explanation:\n\n1. Initialize a variable `res` to 0. This variable will be used to keep track of the count of nodes that meet the specified condition.\n\n2. Define a recursive function `postorder(node)` that takes a `node` as an argument.\n\n3. Inside the `postorder` function:\n   - Check if the current `node` is `None`, indicating an empty subtree or a leaf node. If it is, return a tuple `(0, 0)` representing the sum and number of nodes in the subtree.\n\n   - Recursively call the `postorder` function on the left child of the current node and store the result in the `left` variable.\n\n   - Recursively call the `postorder` function on the right child of the current node and store the result in the `right` variable.\n\n   - Use a `nonlocal` statement to access and update the `res` variable in the outer scope. This variable keeps track of the count of nodes that meet the condition.\n\n   - Calculate the `total_sum` as the sum of the values of the current node, the left subtree, and the right subtree: `total_sum = left[0] + right[0] + node.val`.\n\n   - Calculate the `total_count` as the count of nodes in the current subtree: `total_count = 1 + left[1] + right[1]`.\n\n   - Increment the `res` variable when the condition `node.val == total_sum // total_count` is true. This condition checks if the current node\'s value is equal to the average value of its subtree.\n\n   - Return a tuple `(total_sum, total_count)` representing the updated sum and count for the current subtree.\n\n4. Call the `postorder(root)` function on the root of the binary tree to initiate the post-order traversal and accumulate the count of nodes that meet the condition in the `res` variable.\n\n5. Return the final value of `res`, which represents the count of nodes in the binary tree where the value of the node is equal to the average value of its subtree.\n\nThe code uses a post-order traversal to process the subtrees before processing the current node, which is essential for correctly computing the average values of subtrees.\n\n# Complexity\n- Time complexity: $$O(N)$$\nN is the number of nodes in the binary tree. This is because the code visits each node exactly once during the post-order traversal, and the work done at each node is constant.\n\n- Space complexity: $$O(N)$$\nThis space is used for the recursive call stack during the post-order traversal. In the worst case, if the binary tree is skewed and unbalanced, the space complexity can be O(N). \n\n```python []\nclass Solution:\n    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n        res = 0\n\n        def postorder(node):\n            if not node:\n                return (0, 0) # sum, number of nodes\n            \n            left = postorder(node.left)\n            right = postorder(node.right)\n\n            nonlocal res\n\n            total_sum = left[0] + right[0] + node.val\n            total_count = 1 + left[1] + right[1]\n            res += (node.val == total_sum // total_count)\n\n            return (total_sum, total_count)\n        \n        postorder(root)\n\n        return res\n```\n```javascript []\nvar averageOfSubtree = function(root) {\n    var res = 0;\n\n    var postorder = function(node) {\n        if (!node) {\n            return [0, 0]; // sum, number of nodes\n        }\n\n        var left = postorder(node.left);\n        var right = postorder(node.right);\n\n        var totalSum = left[0] + right[0] + node.val;\n        var totalCount = 1 + left[1] + right[1];\n        res += node.val === Math.floor(totalSum / totalCount);\n\n        return [totalSum, totalCount];\n    };\n\n    postorder(root);\n\n    return res;\n};\n```\n```java []\nclass Solution {\n    private int res = 0;    \n\n    public int averageOfSubtree(TreeNode root) {\n        postorder(root);\n        return res;        \n    }\n\n    private int[] postorder(TreeNode node) {\n        if (node == null) {\n            return new int[]{0, 0}; // sum, number of nodes\n        }\n\n        int[] left = postorder(node.left);\n        int[] right = postorder(node.right);\n\n        int totalSum = left[0] + right[0] + node.val;\n        int totalCount = 1 + left[1] + right[1];\n        res += (node.val == totalSum / totalCount ? 1 : 0);\n\n        return new int[]{totalSum, totalCount};\n    }    \n}\n```\n```C++ []\nclass Solution {\n    int res = 0;\n\npublic:\n    int averageOfSubtree(TreeNode* root) {\n        postorder(root);\n        return res;\n    }\n\n    pair<int, int> postorder(TreeNode* node) {\n        if (!node) {\n            return {0, 0}; // sum, number of nodes\n        }\n\n        auto left = postorder(node->left);\n        auto right = postorder(node->right);\n\n        int totalSum = left.first + right.first + node->val;\n        int totalCount = 1 + left.second + right.second;\n        res += (node->val == totalSum / totalCount);\n\n        return {totalSum, totalCount};\n    }\n};\n```\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u25A0 Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n\u25A0 Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n\n### My next daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/build-an-array-with-stack-operations/solutions/4244407/video-give-me-5-minutes-how-we-think-about-a-solution/\n\nvideo\nhttps://youtu.be/MCYiEw2zvNw\n\n\u25A0 Timeline of the video\n\n`0:04` Basic idea to solve this question\n`1:04` How do you operate each number from the steam of integers?\n`3:34` What operation we need for the two patterns\n`5:17` Coding\n`6:37` Time Complexity and Space Complexity\n\n\n### My previous daily coding challenge post and video.\n\npost\nhttps://leetcode.com/problems/find-mode-in-binary-search-tree/solutions/4233557/video-give-me-5-minutes-how-we-think-about-a-solution-why-do-we-use-inorder-traversal/\n\nvideo\nhttps://youtu.be/0i1Ze62pTuU\n\n\u25A0 Timeline of the video\n`0:04` Which traversal do you use for this question?\n`0:34` Properties of a Binary Search Tree\n`1:31` Key point of my solution code\n`3:09` How to write Inorder, Preorder, Postorder\n`4:08` Coding\n`7:13` Time Complexity and Space Complexity\n\n\n\n\n
['C++', 'Java', 'Python3', 'JavaScript']