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

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❯

Understanding the Problem

A binary tree is considered balanced if, for every node in the tree, the height difference between its left and right subtrees is no more than 1. This ensures that the tree remains approximately balanced in structure, preventing it from becoming skewed like a linked list which would degrade performance in certain operations.

Our goal is to check whether a given binary tree is balanced or not. We need an approach that checks the tree from the bottom up and returns true if all nodes satisfy the height balance condition.

Step-by-Step Solution with Example

Step 1: Define What We Need

To determine if a binary tree is balanced, we must know the height of each subtree and ensure the difference is no more than 1 for every node. We’ll use a recursive approach to calculate the height of subtrees and check the balance condition simultaneously.

Step 2: Understand the Base Case

If the current node is null, we return a height of 0. This acts as the base case in our recursion and also helps us handle empty trees properly.

Step 3: Post-order Traversal to Check Balance

We perform a post-order traversal (left → right → root) so that we can calculate the height of left and right subtrees before checking the balance at the current node.

Step 4: Return Special Flag for Unbalanced Subtrees

Instead of just returning the height, we return -1 if we find any unbalanced subtree. This helps us quickly propagate the unbalanced status upward and avoid unnecessary checks.

Step 5: Apply the Logic on an Example

Let’s take the example tree [3, 9, 20, null, null, 15, 7].

Left subtree rooted at 9 has a height of 1.
Right subtree rooted at 20 has two children: 15 and 7, both leaves. So height is 2.
Difference at root is 1 ⇒ Balanced.
All subtrees also satisfy the condition ⇒ Entire tree is balanced.

Step 6: Visualize an Unbalanced Case

Now consider tree [1, 2, 2, 3, 3, null, null, 4, 4].

Left subtree continues deep into levels 4 and 5.
At one point, difference between heights becomes 2 ⇒ Tree is unbalanced.

We detect this early and bubble up the unbalanced signal.

Edge Cases

Empty Tree: A null tree is considered balanced by definition.
Single Node: A single node with no children is balanced (height difference is 0).
Skewed Trees: Trees where all nodes are only on one side (e.g., linked-list like trees) are unbalanced if their depth exceeds 1 without a corresponding opposite side.

Finally

To solve this problem efficiently, we use a recursive function that checks height and balance together. This avoids redundant computation. The key intuition is that a balanced tree should not have any node where one subtree is taller than the other by more than one level. Handling base cases and special flags for early termination ensures optimal performance even for large trees.

Algorithm Steps❯

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

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int height(TreeNode* node) {
    if (!node) return 0;
    int left = height(node->left);
    int right = height(node->right);
    return (left > right ? left : right) + 1;
}

int isBalanced(TreeNode* root) {
    if (!root) return 1;
    int lh = height(root->left);
    int rh = height(root->right);
    if (abs(lh - rh) > 1) return 0;
    return isBalanced(root->left) && isBalanced(root->right);
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    printf("%s\n", isBalanced(root) ? "true" : "false");
    return 0;
}

⬅ Previous TopicZigzag Traversal of a Binary Tree

Next Topic ⮕Diagonal Traversal of a Binary Tree

Comments

Loading comments...