0110. Balanced Binary Tree

Easy | Tree + DFS | 36 ms (99.59%), 17.9 MB (88.06%)

❓ Problem Statement

Source: LeetCode - Balanced Binary Tree GitHub: Solution / Performance

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

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

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

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [0, 5000].

• -10^4 <= Node.val <= 10^4

💡 Ideas

Instead of calculating the height of each node's subtrees in each iteration, we utilize DFS to return height from the bottom while checking whether each node's subtrees are balanced or not.

Since the minimum height of a tree is 0 (the root is null), we could use '-1' to mark the node with unbalanced subtrees.

🤖 Python3

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # (base case)
        if not root: return True
        if not root.left and not root.right: return True
            
        # ==================================================
        #  Binary Tree + DFS                  (Bottom-up)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        return self.dfs(root) != -1
    
    def dfs(self, node: TreeNode) -> bool:
        if not node: return 0
        if not node.left and not node.right: return 1
        
        leftH = self.dfs(node.left)
        if leftH == -1: return -1
        
        rightH = self.dfs(node.right)
        if rightH == -1: return -1
        
        if abs(leftH - rightH) > 1: return -1
        return max(leftH, rightH) + 1
        
    '''
    def isBalanced(self, root: TreeNode) -> bool:
        # (base case)
        if not root: return True
        if not root.left and not root.right: return True
        
        # ==================================================
        #  Binary Tree                         (Top-down)  =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(n)
            
        return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 \
            and self.isBalanced(root.left) \
            and self.isBalanced(root.right)
            
    def getHeight(self, root) -> int:
        if not root: return 0
        if not root.left and not root.right: return 1
        
        return max(self.getHeight(root.left), self.getHeight(root.right)) + 1
    '''

🤖 Java

class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean isBalanced(TreeNode root) {
        /* base case */
        if(root == null) return true;
        if(root.left == null && root.right == null) return true;
        
        return (dfs(root) != -1) ? true : false;
    }
    
    public int dfs(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        
        int leftH = dfs(root.left);
        if(leftH == -1) return -1;
        
        int rightH = dfs(root.right);
        if(rightH == -1) return -1;
        
        if(Math.abs(leftH - rightH) > 1) return -1;
        return Math.max(leftH, rightH) + 1;
    }
}