How do you solve Balanced Binary Tree on LeetCode?

Balanced Binary Tree (LeetCode #110) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: A tree is height-balanced if the left and right subtrees of every node differ in height by no more than 1.

What is the brute force solution for Balanced Binary Tree?

The brute force approach for Balanced Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. To determine if a binary tree is height-balanced, we can check the height of each subtree for every node. If the height difference between left and right subtrees is more than 1 at any node, the tree is unbalanced. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Balanced Binary Tree?

Balanced Binary Tree uses the following concepts: Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Recursion.

What are the interview tips for Balanced Binary Tree?

Always clarify the definition of 'balanced' with the interviewer. Discuss your thought process and approach before jumping into coding. Consider edge cases and test your solution with them.

What are common mistakes when solving Balanced Binary Tree?

Not considering edge cases like empty trees or single-node trees. Failing to return early when an imbalance is found.

#110

Balanced Binary Tree

Easy

TreeDepth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

We can determine if a tree is balanced by calculating the height of each subtree in a single traversal. If we find any subtree that is unbalanced, we can immediately return false.

⚙️

Algorithm

5 steps

1Step 1: Define a recursive function to calculate the height of the tree and check balance simultaneously.
2Step 2: If a node is null, return height 0.
3Step 3: Recursively check the height of left and right subtrees.
4Step 4: If the height difference is greater than 1, return -1 to indicate unbalance.
5Step 5: Return the height of the current node as 1 + max(left height, right height).

solution.py19 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def isBalanced(self, root: TreeNode) -> bool:
9        def height(node):
10            if not node:
11                return 0
12            left_height = height(node.left)
13            if left_height == -1: return -1
14            right_height = height(node.right)
15            if right_height == -1: return -1
16            if abs(left_height - right_height) > 1:
17                return -1
18            return 1 + max(left_height, right_height)
19        return height(root) != -1

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1A tree is height-balanced if the left and right subtrees of every node differ in height by no more than 1.
2Calculating height and checking balance can be done in a single traversal.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.