Leetcode 110. Balanced Binary Tree (Python)

Related Topic

Depth-First-Search. Tree.

Description

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Sample I/O

Example 1

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

Methodology

This question can be solved by Depth First Search and it is similar with question 104. Maximum Depth of Binary Tree.

From qusetion 104, we learned that to find the maximum depth we need to use dfs and max. For this question, to find if the tree is balanced-height, we need to find left subtree height and right subtree height then get the difference between the left and right subtree. If the difference is greater than 1, then it is not balanced-height otherwise it is balanced-height tree. Note that if there is None node or 1 node, they are both balanced binary tree.

Code

def isBalanced(self, root: TreeNode) -> bool:
    if root is None: return True
    
    def dfs(root):
        if root is None:
            return 0
        return max(dfs(root.left),dfs(root.right))+1
    
    return abs(dfs(root.left)-dfs(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

BigO

We go through each node once therefore the time complexity is O(n) and each node will go to it’s subtree, this cost O(logn). In total is O(nlogn)