Check if Binary Tree is Balanced in DSA C++

Mental Model

A binary tree is balanced if for every node, the height difference between its left and right subtrees is at most one.

Analogy: Imagine a tree with branches on both sides; if one side is much longer than the other, the tree might lean or fall. A balanced tree is like a well-trimmed tree with branches evenly spread.

      1
     / \
    2   3
   / 
  4  

(Heights differ by 1 or less at every node)

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3; 2 has left child 4

Goal: Check if the tree is balanced by verifying height differences at every node

Step 1: Check leaf node 4: left and right children are null, so height is 1

Node 4: height=1, balanced=true

Why: Leaves have height 1 and are balanced by definition

Step 2: Check node 2: left subtree height=1 (from node 4), right subtree is null (height 0)

Node 2: left height=1, right height=0, difference=1, balanced=true

Why: Height difference 1 is allowed, so node 2 is balanced

Step 3: Check node 3: no children, height=1, balanced=true

Node 3: height=1, balanced=true

Why: Leaf node is balanced

Step 4: Check root node 1: left height=2 (from node 2), right height=1 (from node 3), difference=1

Node 1: balanced=true

Why: Height difference at root is 1, so tree is balanced

Result:

1 (root) balanced=true
Final answer: Tree is balanced

Annotated Code

DSA C++

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Returns height if balanced, -1 if not balanced
int checkHeight(TreeNode* root) {
    if (!root) return 0; // empty subtree height 0

    int leftHeight = checkHeight(root->left); // check left subtree
    if (leftHeight == -1) return -1; // left subtree not balanced

    int rightHeight = checkHeight(root->right); // check right subtree
    if (rightHeight == -1) return -1; // right subtree not balanced

    if (abs(leftHeight - rightHeight) > 1) return -1; // current node not balanced

    return max(leftHeight, rightHeight) + 1; // height of current node
}

bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);

    cout << (isBalanced(root) ? "Tree is balanced" : "Tree is not balanced") << endl;
    return 0;
}

int leftHeight = checkHeight(root->left); // check left subtree

recursively get height of left subtree

if (leftHeight == -1) return -1; // left subtree not balanced

stop early if left subtree is unbalanced

int rightHeight = checkHeight(root->right); // check right subtree

recursively get height of right subtree

if (rightHeight == -1) return -1; // right subtree not balanced

stop early if right subtree is unbalanced

if (abs(leftHeight - rightHeight) > 1) return -1; // current node not balanced

check height difference at current node

return max(leftHeight, rightHeight) + 1; // height of current node

return height if balanced

Output

Tree is balanced

Complexity Analysis

Time: O(n) because we visit each node once to compute heights and check balance

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach recomputes heights repeatedly causing O(n^2) time; this method computes height and balance in one pass for O(n) time

Edge Cases

Empty tree

Returns balanced because empty tree has height 0 and no imbalance

DSA C++

if (!root) return 0; // empty subtree height 0

Single node tree

Returns balanced because single node has no children and height difference 0

DSA C++

if (!root) return 0; // empty subtree height 0

Unbalanced tree with large height difference

Returns not balanced (-1) as soon as difference > 1 is found

DSA C++

if (abs(leftHeight - rightHeight) > 1) return -1; // current node not balanced

When to Use This Pattern

When a problem asks if a tree is balanced, use a bottom-up height check with early stopping to efficiently detect imbalance.

Common Mistakes

Mistake: Calculating height separately for left and right subtrees multiple times causing O(n^2) time
Fix: Combine height calculation and balance check in one recursive function with early return

Mistake: Not stopping recursion early when imbalance is found, wasting time
Fix: Return -1 immediately when imbalance detected to stop further checks

Summary

Checks if a binary tree is balanced by verifying height differences at every node.

Use when you need to confirm tree balance efficiently in one traversal.

The key is to return height or -1 for imbalance in one recursive pass with early stopping.