110. Balanced Binary Tree
Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Recursion
FAANG asked: 1
Acceptance rate: 44.8%
Problem Breakdown
The problem asks us to determine if a given binary tree is height-balanced. A binary tree is considered height-balanced if for every node in the tree, the heights of its left and right subtrees differ by no more than 1.
Inputs:
root: The root node of the binary tree.
Outputs:
- A boolean value indicating whether the tree is height-balanced (
true) or not (false).
Implicit Constraints/Edge Cases:
- An empty tree (
[]) should returntruesince there are no nodes to violate the balance condition. - The tree can have up to 5000 nodes, so the solution should be efficient in terms of both time and space.
Intuition
A brute-force approach would involve checking the height difference for every node in the tree. This would result in a time complexity of O(n^2) because for each node, we might have to traverse its entire subtree to calculate heights.
The key insight is to use a bottom-up approach where we calculate the height of subtrees while also checking if they are balanced. This way, we can determine the balance condition and height in a single traversal, reducing the time complexity to O(n).
Approach
- Define a Helper Function: Create a helper function that returns two values: whether the subtree is balanced and its height.
- Base Case: If the current node is
null, return(true, 0)indicating an empty tree is balanced with height 0. - Recursive Case:
- Recursively check the left and right subtrees.
- If either subtree is not balanced, propagate this information upwards.
- Calculate the height of the current node as
1 + max(left_height, right_height). - Check if the current node is balanced by ensuring the height difference between its left and right subtrees is no more than 1.
- Return Result: Use the helper function to determine if the entire tree is balanced.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
- Space Complexity: O(h), where h is the height of the tree. This accounts for the recursion stack space.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isBalanced(root: TreeNode) -> bool:
def check_balance(node):
if not node:
return (True, 0)
left_balanced, left_height = check_balance(node.left)
right_balanced, right_height = check_balance(node.right)
balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
height = 1 + max(left_height, right_height)
return (balanced, height)
return check_balance(root)[0]
Edge Cases Handled
- Empty Tree: The function correctly returns
truefor an empty tree. - Skewed Trees: Handles cases where the tree is heavily skewed to one side.
- Balanced Trees: Correctly identifies trees that are perfectly balanced.
- Unbalanced Trees: Properly identifies and returns
falsefor unbalanced trees.