Given a binary tree, determine if it is height-balanced.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Explanation: The maximum depth of the left subtree (9) is 1, and the maximum depth of the right subtree (20, 15, 7) is 2. The difference is 1, so this part of the tree is balanced. Checking all other nodes also confirms it's balanced.
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: The left subtree has a depth of 3, while the right subtree has a depth of 1. The absolute difference is 2, which is greater than 1. Therefore, the tree is not height-balanced.
Example 3:
Input: root = []
Output: true
Explanation: An empty tree is considered balanced.
Write a function that takes the root of a binary tree as input and returns true
if the tree is height-balanced, and false
otherwise. Your solution should be efficient in terms of both time and space complexity.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to check if a tree is balanced is like thoroughly inspecting every single branch. We look at each part of the tree to measure how far it extends down each side.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def is_balanced_brute_force(root):
if not root:
return True
left_height = get_height(root.left)
right_height = get_height(root.right)
# If height difference is > 1, tree unbalanced.
if abs(left_height - right_height) > 1:
return False
# Recursively check if left and right subtrees are balanced.
return is_balanced_brute_force(root.left) and \
is_balanced_brute_force(root.right)
def get_height(node):
if not node:
return 0
left_subtree_height = get_height(node.left)
right_subtree_height = get_height(node.right)
# Add 1 to account for the current node itself.
return max(left_subtree_height, right_subtree_height) + 1
The most efficient way to check if a tree is balanced is to look at each part only once. We can do this by checking the height of each subtree and if it is balanced at the same time, working our way up from the leaves.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_balanced_binary_tree(root):
def check_balance(node):
if not node:
return 0, True
left_height, is_left_balanced = check_balance(node.left)
right_height, is_right_balanced = check_balance(node.right)
# If either subtree is unbalanced, the whole tree is unbalanced
if not is_left_balanced or not is_right_balanced:
return 0, False
height_difference = abs(left_height - right_height)
# Height difference greater than 1 means it's not balanced
if height_difference > 1:
return 0, False
current_height = max(left_height, right_height) + 1
return current_height, True
_, is_balanced = check_balance(root)
return is_balanced
Case | How to Handle |
---|---|
Null root node | A null tree is considered balanced, so return true immediately. |
Single node tree | A single node tree is balanced, so return true. |
Perfectly balanced tree | The algorithm should efficiently handle perfectly balanced trees with minimal recursion depth. |
Completely unbalanced tree (left or right skewed) | The algorithm should correctly identify an unbalanced tree in worst-case scenarios, even if it leads to O(n) recursion depth. |
Tree with large height differences between subtrees at a deep level | The height check should propagate back up to the root to correctly identify imbalance even at deeper levels. |
Tree with very large number of nodes (potential stack overflow with recursion) | Consider alternative iterative approach to prevent stack overflow in extremely deep trees. |
Tree where height calculations result in integer overflow | Ensure the chosen data type (e.g., int) for height calculations is sufficient or use long to avoid overflow. |
Tree with duplicate values, affecting subtree balancing | The algorithm's correctness is independent of the node values themselves, and it depends only on the height of subtrees. |