Skip to content

110. Balanced Binary Tree 👍

Approach 1: Straightforward $O(n\log n)$

  • Time: $O(n\log n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  bool isBalanced(TreeNode* root) {
    if (root == nullptr)
      return true;
    return abs(maxDepth(root->left) - maxDepth(root->right)) <= 1 &&
           isBalanced(root->left) && isBalanced(root->right);
  }

 private:
  int maxDepth(TreeNode* root) {
    if (root == nullptr)
      return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public boolean isBalanced(TreeNode root) {
    if (root == null)
      return true;
    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && //
        isBalanced(root.left) &&                                        //
        isBalanced(root.right);
  }

  private int maxDepth(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def isBalanced(self, root: TreeNode | None) -> bool:
    if not root:
      return True

    def maxDepth(root: TreeNode | None) -> int:
      if not root:
        return 0
      return 1 + max(maxDepth(root.left), maxDepth(root.right))

    return (abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 and
            self.isBalanced(root.left) and
            self.isBalanced(root.right))

Approach 2: Straightforward $O(n)$

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  bool isBalanced(TreeNode* root) {
    bool ans = true;
    maxDepth(root, ans);
    return ans;
  }

  // Returns the height of root and sets ans to false if root unbalanced.
  int maxDepth(TreeNode* root, bool& ans) {
    if (root == nullptr || !ans)
      return 0;
    const int left = maxDepth(root->left, ans);
    const int right = maxDepth(root->right, ans);
    if (abs(left - right) > 1)
      ans = false;
    return max(left, right) + 1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public boolean isBalanced(TreeNode root) {
    maxDepth(root);
    return ans;
  }

  private boolean ans = true;

  // Returns the height of root and sets ans to false if root unbalanced.
  public int maxDepth(TreeNode root) {
    if (root == null || !ans)
      return 0;
    final int left = maxDepth(root.left);
    final int right = maxDepth(root.right);
    if (Math.abs(left - right) > 1)
      ans = false;
    return Math.max(left, right) + 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def isBalanced(self, root: TreeNode | None) -> bool:
    ans = True

    def maxDepth(root: TreeNode | None) -> int:
      """Returns the height of root and sets ans to false if root unbalanced."""
      nonlocal ans
      if not root or not ans:
        return 0
      left = maxDepth(root.left)
      right = maxDepth(root.right)
      if abs(left - right) > 1:
        ans = False
      return max(left, right) + 1

    maxDepth(root)
    return ans

Approach 3: Heuristic $O(n)$

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  bool isBalanced(TreeNode* root) {
    return maxDepth(root) != -1;
  }

 private:
  // Returns the height of root if root is balanced; otherwise, returns -1.
  int maxDepth(TreeNode* root) {
    if (root == nullptr)
      return 0;

    const int left = maxDepth(root->left);
    if (left == -1)
      return -1;
    const int right = maxDepth(root->right);
    if (right == -1)
      return -1;
    if (abs(left - right) > 1)
      return -1;

    return 1 + max(left, right);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public boolean isBalanced(TreeNode root) {
    return maxDepth(root) != -1;
  }

  // Returns the height of root if root is balanced; otherwise, returns -1.
  private int maxDepth(TreeNode root) {
    if (root == null)
      return 0;

    final int left = maxDepth(root.left);
    if (left == -1)
      return -1;
    final int right = maxDepth(root.right);
    if (right == -1)
      return -1;
    if (Math.abs(left - right) > 1)
      return -1;

    return 1 + Math.max(left, right);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def isBalanced(self, root: TreeNode | None) -> bool:
    def maxDepth(root: TreeNode | None) -> int:
      """Returns the height of root if root is balanced; otherwise, returns -1."""
      if not root:
        return 0

      left = maxDepth(root.left)
      if left == -1:
        return -1
      right = maxDepth(root.right)
      if right == -1:
        return -1
      if abs(left - right) > 1:
        return -1

      return 1 + max(maxDepth(root.left), maxDepth(root.right))

    return maxDepth(root) != -1