January 13, 2019

110. Balanced Binary Tree

Solution 1

This is not an optimal solution. The time complexity is O(nlogn).

Analysis:

O(n) + 2`*O(n/2) + 4*O(n/4) + … = O(nlogn)

Level 1: (getHeight left) n/2 + (getHeight right) n/2 = n
Level 2: n/4 + n/4 + n/4 + n/4 = n
…. For every level, worst case is O(n) In the worst case, there’re logn levels Thus total time complexity is O(nlogn)

space complexity is O(h)

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        if abs(self.getHeight(root.left) - self.getHeight(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
        
        
    def getHeight(self, root):
        if not root:
            return 0
        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

Solution 2

There are three situations the tree is unbalanced: 1) It’s left subtree is unbalanced 2) It’s right subtree is unbalanced 3) The absolute value between the height of its left subtree and its right subtree is greater than 1

Thus we redefine getHeight method:

Return height if it’s balanced
Return -1 id it’s unbalanced

In this case, total time complexity is O(n) - check left and right node in every recursion to avoid further useless search

space complexity is O(h)

Java:

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (getHeight(root) == -1) {
            return false;
        }
        return true;
        
    }
    
    private int getHeight(TreeNode root) {
        
        if (root == null) {
            return 0;
        }
        
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        
        return Math.max(left, right) + 1;
        
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        height = self.getHeight(root)
        if height == -1:
            return False
        return True
        
    def getHeight(self, root):
        if not root:
            return 0
        left = self.getHeight(root.left)
        right = self.getHeight(root.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)