110. Balanced Binary Tree

Approach 1: DFS (Naive)

In the naive approach, we calculate the height of each subtree and check if the difference in heights is greater than 1. If it is, the tree is not balanced. Recursive calls are made for each subtree.

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

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def getHeight(node):
            if not node:
                return 0

            leftSub = getHeight(node.left)
            rightSub = getHeight(node.right)

            return 1 + max(leftSub, rightSub)

        if not root:
            return True

        leftHeight = getHeight(root.left)
        rightHeight = getHeight(root.right)

        if abs(leftHeight - rightHeight) > 1:
            return False

        return self.isBalanced(root.left) and self.isBalanced(root.right)

Time: $O(n^2)$ — where $n$ is the number of nodes in the tree.
Space: $O(h)$ — where $h$ is the height of the tree.

This approach uses a bottom-up depth-first search to calculate the height of each subtree and check if it is balanced. The key idea is to compute the height while checking balance simultaneously, return early if an unbalanced subtree is found. This allows early termination.

Algorithm:

Check the height of the left and right subtrees.
If the height difference is greater than 1, the tree is not balanced.
Otherwise, the tree is balanced.

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

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def checkHeight(node):
            if not node:
                return 0

            leftSub = checkHeight(node.left)
            if leftSub == -1:
                return -1

            rightSub = checkHeight(node.right)
            if rightSub == -1:
                return -1

            if abs(rightSub-leftSub) > 1:
                return -1

            return 1 + max(leftSub, rightSub)

        return checkHeight(root) != -1

Time: $O(n)$ — where $n$ is the number of nodes in the tree.
Space: $O(h)$ — where $h$ is the height of the tree.

Last updated on

110. Balanced Binary Tree

Approach 1: DFS (Naive)

Approach 2: DFS (Bottom-Up)

On this page