Balanced Binary Tree https://leetcode.com/problems/balanced-binary-tree/?tab=Description
- Traverse and find height at each node. Test if it is balanced and subsequently recursively call on root.left and root.right. What is time complexity? How many times is node "touched" or called? Answer is at max "h" times (i.e. path from node to root), where h is the height of the tree. Visualize it. Now if the tree is balanced, we have O(NLgN), otherwise worst case is O(N^2). The accurate complexity is O(Nh) and space complexity is O(h).
- Optimization is using post order traversal - test height and balance in one call and propogate it upwards. In Python, we can return two variables. In other languages, we can return an error code in height. Complexity O(N) and space is O(h).
class Solution(object): def helper(self, root): if root == None: return 0, True hl, lb = self.helper(root.left) hr, rb = self.helper(root.right) if lb and rb and abs(hl-hr) <= 1: return max(hl,hr) + 1, True else: return -1, False def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ h, is_b = self.helper(root) return is_b