Check if a Binary Tree is Balanced - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given the root of a binary tree, determine if the tree is height-balanced. A binary tree is considered balanced if, for every node, the height difference between its left and right subtrees is not more than 1.

Examples❯

Input Tree Level Order Output Description
[1, 2, 3, 4, 5, null, 6]
[[1], [2, 3], [4, 5, 6]] Balanced tree with nodes at varying depths but height difference ≤ 1
[1]
[[1]] Single-node tree, always balanced
[] [] Empty tree (no nodes) is trivially balanced
[1, 2, null, 3, null, null, null, 4]
[[1], [2], [3], [4]] Unbalanced tree: left-heavy, depth difference > 1 between subtrees
[1, null, 2, null, null, null, 3]
[[1], [2], [3]] Unbalanced tree: right-skewed with depth difference > 1
[10, 20, 30, 40, null, null, 50]
[[10], [20, 30], [40, 50]] Balanced tree: height difference between left and right subtrees is 0

Visualization Player

Solution❯

Case 1: Empty Tree

If the input tree is empty (i.e., the root is null), it is considered balanced. This is because there are no nodes to create an imbalance, and thus by definition, it meets the criteria of a balanced tree.

Case 2: Balanced Binary Tree

In a balanced binary tree, the height difference between the left and right subtrees of any node is no more than 1. For example, consider the tree [3, 9, 20, null, null, 15, 7]. The left subtree (rooted at 9) has a height of 1 and the right subtree (rooted at 20) has a height of 2. Since the difference is just 1, the tree is considered balanced. We continue this check recursively for each node.

Case 3: Unbalanced Binary Tree

When one subtree is significantly deeper than the other, the tree is unbalanced. For example, in the tree [1, 2, 2, 3, 3, null, null, 4, 4], the left subtree continues for four levels while the right is much shallower. When checking from the bottom-up, we find that at the node with value 2 (on the left), the difference in height between its left and right children exceeds 1. This disqualifies the entire tree from being balanced.

How to Check

To determine if a tree is balanced, we use a recursive approach that checks the height of each subtree. At each node, we compute the height of the left and right subtrees. If at any node the difference exceeds 1, or if any subtree is already found to be unbalanced, the entire tree is unbalanced. If we finish all checks without violating this condition, the tree is balanced.

Algorithm Steps❯

  1. Given a binary tree, if the tree is empty, it is considered balanced.
  2. Recursively compute the height of the left and right subtrees.
  3. If the absolute difference between the left and right subtree heights is more than 1, the tree is not balanced.
  4. Recursively check that both the left subtree and the right subtree are balanced.
  5. If all checks pass, the binary tree is balanced.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def isBalanced(root):
    def height(node):
        if not node:
            return 0
        return max(height(node.left), height(node.right)) + 1
    if not root:
        return True
    leftHeight = height(root.left)
    rightHeight = height(root.right)
    if abs(leftHeight - rightHeight) > 1:
        return False
    return isBalanced(root.left) and isBalanced(root.right)

# Example usage:
if __name__ == '__main__':
    # Construct a binary tree:
    #         1
    #        / \
    #       2   3
    #      /
    #     4
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
    print(isBalanced(root))