Balanced Binary Tree

TreesDFS

15 min

Problem Statement

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]

Output: false

Solution (Depth-First Search)

We can solve this problem using a recursive Depth-First Search (DFS) approach. For each node, we'll calculate the height of its left and right subtrees.

The key is to combine the height calculation and the balance check in a single recursive function. This function will return the height of a subtree if it's balanced, or a special value (like -1) if it's not. This avoids re-calculating heights and makes the solution efficient.

Algorithm Steps

Create a recursive helper function, `dfs(node)`.
Base Case: If `node` is null, it's a balanced subtree of height 0. Return 0.
Recursively call `dfs` on the left and right children to get their heights.
If either recursive call returns -1, it means a subtree is unbalanced, so propagate -1 up.
Check if the absolute difference between the left and right heights is greater than 1. If it is, the current node is unbalanced, so return -1.
If the node is balanced, return its height: `1 + max(left_height, right_height)`.
The initial call to `dfs(root)` will determine if the entire tree is balanced if the result is not -1.

DFS on node 3. Recursing on left child.

Balanced Binary Tree Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(root):
            if not root:
                return [True, 0]
            
            left, right = dfs(root.left), dfs(root.right)
            
            balanced = (left[0] and right[0] and
                        abs(left[1] - right[1]) <= 1)
            
            return [balanced, 1 + max(left[1], right[1])]
        
        return dfs(root)[0]