Python solution with detailed explanation


  • 0
    G

    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
    

Log in to reply
 

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