Python solution with detailed explanation

• Solution

Balanced Binary Tree https://leetcode.com/problems/balanced-binary-tree/?tab=Description

Brute Force

• 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).

Post-Order Algorithm

• 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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.