#110

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Balanced Binary Tree

Determine if a binary tree is height-balanced using tree traversal and state tracking techniques.

Problem Statement

You are given the root of a binary tree. A binary tree is considered balanced if the left and right subtrees of every node differ in height by at most one. Return true if the tree is balanced, otherwise return false.

For example, for a binary tree with nodes [3,9,20,null,null,15,7], the tree is balanced. However, a tree like [1,2,2,3,3,null,null,4,4] is unbalanced due to a large height difference between subtrees.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Example 3

Input: root = []

Output: true

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104

Solution Approach

Tree Traversal with Height Calculation

A Depth-First Search (DFS) traversal can be used to visit every node of the tree. While traversing, we will compute the height of the left and right subtrees for each node. The tree is balanced if the difference between these heights is at most 1. The traversal continues until all nodes are checked or an imbalance is detected early.

State Tracking for Early Termination

While computing heights during DFS, keep track of any imbalance condition (difference of height greater than 1). If an imbalance is detected at any point, we can stop further traversal and immediately return false. This avoids unnecessary work and improves efficiency.

Time and Space Complexity Considerations

The time complexity for this approach depends on the total number of nodes in the tree, as every node needs to be visited. Therefore, the time complexity is O(n), where n is the number of nodes. The space complexity also depends on the depth of the tree, which, in the worst case, is O(n) for a skewed tree, or O(log n) for a balanced tree.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) due to the DFS traversal, as each node is visited once. The space complexity is O(h), where h is the height of the tree, because of the recursive call stack in DFS. In the worst case, the height could be n (a skewed tree), resulting in O(n) space complexity.

What Interviewers Usually Probe

Do you understand the difference between balanced and unbalanced trees?
Can you explain how DFS helps in both height calculation and detecting imbalances?
Will you handle edge cases like an empty tree or a skewed tree efficiently?

Common Pitfalls or Variants

Common pitfalls

Not handling edge cases like an empty tree, which should return true.
Missing the early termination by not checking imbalance during traversal, leading to unnecessary work.
Incorrectly calculating the height of subtrees, which can cause false results in balance checking.

Follow-up variants

Check if the tree is a full binary tree.
Find the diameter of the tree, which is the longest path between any two nodes.
Determine if a binary tree is perfect, meaning all leaf nodes are at the same level and every parent has two children.

FAQ

What is a height-balanced binary tree?

A height-balanced binary tree is one where, for every node, the height difference between the left and right subtrees is at most one.

How do you calculate the height of a binary tree node?

The height of a node is calculated as 1 plus the maximum height of its left and right subtrees.

What happens if the tree is unbalanced?

If the difference in height between any two subtrees of a node exceeds 1, the tree is considered unbalanced, and the function should return false.

What should you do if an imbalance is found during DFS?

If an imbalance is found during DFS, you should immediately return false without continuing the traversal, as further checks are unnecessary.

How do you handle an empty tree?

An empty tree is considered balanced by definition, so the function should return true for this case.

terminal

Solution

Solution 1: Bottom-Up Recursion

We define a function $height(root)$ to calculate the height of a binary tree, with the following logic:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 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 height(root):
            if root is None:
                return 0
            l, r = height(root.left), height(root.right)
            if l == -1 or r == -1 or abs(l - r) > 1:
                return -1
            return 1 + max(l, r)

        return height(root) >= 0

Continue Practicing

#111 minimum depth of binary tree #112 path sum #113 path sum ii