Balanced Binary Tree

Problem

https://leetcode.com/problems/balanced-binary-tree/

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

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

Example 3:

Input: root = []
Output: true

Constraints:

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

• -10:sup:`4`<= Node.val <= 10:sup:`4`

Pattern

Tree, Depth-First Search, Binary Tree

Approaches

DFS

Explanation

For a binary tree to be height-balanced, the left and right subtrees of every node must differ in max height by no more than 1. We can use depth-first search to traverse the tree and calculate the max height of each tree.

If root is None, the height of a tree is 0. Otherwise, the height of a tree is the 1 plus the maximum of the heights of the left and right subtrees. If we encounter a subtree that is not balanced, we set a global variable is_balanced to false.

Code

from __future__ import annotations

from collections import deque


class TreeNode:
    """Node in a binary tree."""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    @classmethod
    def from_list(cls, vals: list[int | None]) -> TreeNode | None:
        if not vals:
            return None

        root = cls(vals[0])
        queue = deque([root])
        children = iter(vals[1:])

        while queue:
            node = queue.popleft()
            for side in ("left", "right"):
                val = next(children, None)
                if val is not None:
                    child = cls(val)
                    setattr(node, side, child)
                    queue.append(child)

        return root


def isBalanced(root: TreeNode | None) -> bool:
    """Return whether the binary tree is height-balanced."""
    is_balanced = True

    def dfs(node: TreeNode | None) -> int:
        nonlocal is_balanced

        if node is None:
            return 0

        left = dfs(node.left)
        right = dfs(node.right)

        if abs(left - right) > 1:
            is_balanced = False

        return 1 + max(left, right)

    dfs(root)
    return is_balanced

Test

>>> from balanced_binary_tree__dfs import TreeNode, isBalanced
>>> isBalanced(TreeNode.from_list([3, 9, 20, None, None, 15, 7]))
True
>>> isBalanced(TreeNode.from_list([1, 2, 2, 3, 3, None, None, 4, 4]))
False
>>> isBalanced(TreeNode.from_list([]))
True

Complexity

\(n\) is the number of nodes in the tree, and \(d\) is the maximum depth of the tree

Measure	Complexity	Notes
Time	\(O(n)\)	visit every node in the tree
Auxiliary Space	\(O(d)\)	recursive call stack

class balanced_binary_tree__dfs.TreeNode(val=0, left=None, right=None)

Bases: object

Node in a binary tree.

classmethod from_list(vals: list[int | None]) → TreeNode | None

balanced_binary_tree__dfs.isBalanced(root: TreeNode | None) → bool

Return whether the binary tree is height-balanced.