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

💡 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