⭐ JS | Simple & Explained | Post Order
110. Balanced Binary Tree \uD83D\uDE80\n\n### Solution Developed In:\n\n\n## The Question\nFor this article we will be covering Leetcode\'s \'110. Balanced Bina
# 110. Balanced Binary Tree \uD83D\uDE80\n\n### Solution Developed In:\n![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)\n\n## The Question\nFor this article we will be covering Leetcode\'s \'[110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/discuss/2051735/JS-or-Simple-and-Explained-or-Post-Order)\' question. \n\nQuestion:\n\n> Given a **binary tree**, determine if it is **height-balanced**.\n> For this problem, a **height-balanced** binary tree is defined as:\n>> a binary tree in which the left and right subtrees of every node **differ in height by no more than 1**.\n\n\nExample:\n\n>![Example](https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg)\n\n```\nInput: root = [3,9,20,null,null,15,7]\nOutput: true\n```\n\n## Explaining The Question\nThis Question is rated **Easy**. Which is for the most part accurate. I do not believe that this question is easy to solve although. You need to know a handful of techniques and patterns to be able to solve this. \n\nThis question is very close to the [**Maximum Depth of Binary Tree**](https://leetcode.com/problems/maximum-depth-of-binary-tree/). Although in this case, we\'re going to need to keep track of the height of every **subtree** on every **node**, so we can ask the question \'Does my left or right tree differ in height by 1?\'.\n\nWhat Leetcode has asked us to do is to determine if the tree is **height-balanced**. Which is a **Binary Tree** in which the left and right subtrees of every node differ in height by no more than 1.\n\n##  Recommended Knowledge\n1. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)\n2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)\n3. [Post Order Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Post-order)\n4. [**Maximum Depth of Binary Tree**](https://leetcode.com/problems/maximum-depth-of-binary-tree)\n5. [Recursive Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)\n\n## What do we know?\n1. We have a ***binary tree*** (Most times, it could be empty)\n2. We need to find the height of the left and right subtrees of **every node**. \n\n## How we\'re going to do it:\n\nWe\'re going to use [Post Order Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Post-order) to find the height of the left and right subtrees of **every node**. We do this by passing a **height** parameter to the each subtree, counting the number of nodes it takes until it hits the bottom of the tree. Meaning that once it hits the bottom most node, we have found the height of the tree.\n\nNow we know the height of the left and right subtrees. All we do now is ask, \'Does my left or right tree differ in height by 1?\'. If any of them violate this, we set our flag to false. \n\n1. Set ourself a `flag` to true. So by default, we\'re going to assume that the tree is height-balanced. Until we find a node that violates this, we\'re going to set our flag to false.\n2. Perform a post order traversal of the tree. Where we pass a `height` parameter to each node.\n3. Which gives us the left and right heights of each node. \n4. We ask the question, \'Does my left or right tree differ in height by 1?\'. If any of them violate this, we set our flag to false.\n\n## Big O Notation:\n* Time Complexity:   *O(**n**)* | Where ***n*** is the number of nodes in our ***Binary Tree*** | As we\'re going to traverse all of the nodes within the tree.\n  \n* Space Complexity: *O(**n**)* | Where ***n*** is the number of nodes in our ***Binary Tree*** | As in the worst case, we\'re going to have to store the entire height of the tree in the call stack. \n\n## Leetcode Results:\n\nSee Submission Link: \n\n* Runtime: 70 ms, faster than ***95.74%*** of JavaScript online submissions for Balanced Binary Tree\n* Memory Usage: 47.1 MB, less than ***63.74%*** of JavaScript online submissions for Balanced Binary Tree\n\n[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/702266058/)\n\n\n***\n\n# The Solution\n```\n/**\n * Definition for a binary tree node.\n * function TreeNode(val, left, right) {\n * this.val   = (val===undefined ? 0 : val)\n * this.left  = (left===undefined ? null : left)\n * this.right = (right===undefined ? null : right)\n * }\n */\n/**\n * @param {TreeNode} root\n * @return {boolean}\n */\nvar isBalanced = function (root) {\n\n    // A flag to check if the tree is balanced or not\n    let flag = true;\n\n    // Helper function to check if the tree is balanced or not\n    const get_heights = (node, height) => {\n\n        // Empty tree? It\'s 0 in height\n        if (!node) {\n            return 0;\n        }\n\n        // Get my left and right heights\n        // by adding 1 to the height of the left and right subtrees.\n        // each time we move down them\n        const left_height  = get_heights(node.left, height + 1);\n        const right_height = get_heights(node.right, height + 1);\n\n        // Let\'s use some math.\n        // Technically, if we have a balanced tree, the difference\n        // should always be 0. But because, this question is awkward, we need to check if \n        // if its diff is greater than 1. So we minus the two by using absolutes values and asking\n        // if the diff in this sub tree was greater than 1. If so bad un balanced.\n        if (Math.abs(right_height - left_height) > 1) {\n            flag = false;\n        }\n\n        // Return the height of the tree\n        // By returning whoever had the bigger height and adding 1 (Our current node)\n        return Math.max(left_height, right_height) + 1;\n    };\n\n    // Call the helper function\n    get_heights(root, 0);\n\n    // Get the flag back to base. :D\n    return flag;\n};\n\n```
['JavaScript']