O(N) DFS Beats 99.78% 🔥 Explained Line by Line
\ndef isBalanced(self, root: Optional[TreeNode]) -> bool:\n\t# helper method to determine the height of a node\n\t# however it will return False if the tree beg
```\ndef isBalanced(self, root: Optional[TreeNode]) -> bool:\n\t# helper method to determine the height of a node\n\t# however it will return False if the tree beginning at node is not height-balanced\n\tdef dfs(node):\n\t\tif not node: # if there is no node then return 1\n\t\t\treturn 1 # this will be our lowest height\n\t\tleft = dfs(node.left) # get the height of the left subtree\n\t\tright = dfs(node.right) # get the height of the right subtree\n\t\t# if either subtree is NOT height balanced, then the whole tree is not height-balanced\n\t\tif left == False or right == False or abs(left-right)>1: # if the heights of the subtrees are not within 1 of each other, then the tree isn\'t height-balanced\n\t\t\treturn False # this tree is not height-balanced\n\t\treturn max(left,right) + 1 # the height of this tree is 1 more than the maximum height of the subtrees\n\treturn dfs(root) != False # if we never returned False then we never found a height-balancing issue!\n```\nThe main idea is that we will use a helper method, `dfs`, to figure out the height of a node while also checking to see if it is height balanced! Basically, we do exactly what we would do for a regular recursive method to figure out the height of a tree \u2013 return the maximum of the heights of the left and right subtrees, plus one. However, if the tree is not height balanced (`abs(left-right)>1`), then we need to return `False`. But before we check that, we also need to check if either of the subtrees are not balanced \u2013\u2013\xA0if `left == False or right == False` then they are not height-balanced, so the whole tree isn\'t height balanced either! This method only requires us to look at every node once, giving a time complexity of `O(N)`, and making this a super fast solution!
['Depth-First Search', 'Python']