Python solution with detailed explanation

  • 0


    Balanced Binary Tree

    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
                return -1, False
        def isBalanced(self, root):
            :type root: TreeNode
            :rtype: bool
            h, is_b = self.helper(root)
            return is_b

Log in to reply

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