javascript DFS post-order recursive solution and BFS iterative solution
Here I would like to share the DFS approach first, BFS approach (not so elegant but intuitive and can be considered as brute force) will follow after. Please up
Here I would like to share the DFS approach first, BFS approach (*not so elegant but intuitive and can be considered as brute force*) will follow after. Please upvote if it is helpful :)\nThe idea is to traverse through the tree and do something at the node (via a ```traverse(node)``` function + checking the average of the subtree). Hence carrying out a post-order depth-first traversal seems to be logically here (as we have to traverse all before comparing the average).\nHowever, we need to specifying the output of the recursive function, as we need to use the sum of all nodes in the subtree (left and right each) as well as the nodes count, we have to return it for further usage. Finally using closures concept, we can put this ```traverse(node)``` function inside our main function and set ```count``` to track whenever a node (and its subtree) satisfy the required condition.\nBelow is the implementation of DFS approach.\n```\nvar averageOfSubtree = function(root) {\n    let count = 0;\n    \n    function traverse(node) {\n        if (node === null) {\n            return [0, 0];\n        }\n\n        let [sumLeft, countLeft] = traverse(node.left);\n        let [sumRight, countRight] = traverse(node.right);\n\n        if (Math.floor((sumLeft + sumRight + node.val) / (countLeft + countRight + 1)) === node.val) {\n            count++;\n        }\n\n        return [sumLeft + sumRight + node.val, countLeft + countRight + 1];\n    }\n    \n    traverse(root);\n    \n    return count;\n};\n```\n\nFor BFS, it is intuitive that we want to traverse through the tree, going to all nodes level by level, at each node, we will determine if it is a ```valid``` node satisfying the required condition. \nHence, we can use BFS two times, one is to just traverse the tree, and the other is to traverse the subtree of the node being traversed and checking the condition.\nBelow is the BFS approach implementation. This algorithm is not optimal but it offers another perspective and fun view for dealing with trees :)\n```\nvar averageOfSubtree = function(root) {\n    let count = 0;\n\t\n    let queue = [];\n    if (root === null) return 0;\n    queue.push(root);\n    while (queue.length) {\n        let node = queue.shift();\n        if (isValid(node)) {\n            count++;\n        }\n        if (node.left !== null) {\n            queue.push(node.left);\n        }\n        if (node.right !== null) {\n            queue.push(node.right);\n        }\n    }\n    return count;\n};\n\nvar isValid = function(node) {\n    let sum = 0;\n    let count = 0;\n\t\n\tlet queue = [];\n    if (node === null) return false;\n    queue.push(node);\n    \n    while (queue.length) {\n        let node = queue.shift();\n        sum += node.val;\n        count++;\n        if (node.left !== null) {\n            queue.push(node.left);\n        }\n        if (node.right !== null) {\n            queue.push(node.right);\n        }\n    }\n    if (Math.floor(sum / count) === node.val) return true;\n    return false;\n}\n```
['Depth-First Search', 'Breadth-First Search', 'JavaScript']