Domain 1EasyCORE

Balanced Binary Tree

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Recursion

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 return true since 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

  1. Define a Helper Function: Create a helper function that returns two values: whether the subtree is balanced and its height.
  2. Base Case: If the current node is null, return (true, 0) indicating an empty tree is balanced with height 0.
  3. 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.
  4. 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 true for 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 false for unbalanced trees.