Check if a Binary Tree is Balanced

Problem and examples

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.

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

Explore Check if a Binary Tree is Balanced

Load an example or enter your own input. Use the player controls to follow each change.

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.

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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

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

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

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

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

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) ? "true" : "false") << endl;
    return 0;
}

Python implementation

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
    lh = height(root.left)
    rh = height(root.right)
    if abs(lh - rh) > 1:
        return False
    return isBalanced(root.left) and isBalanced(root.right)

# Example usage
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
    print(isBalanced(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class BalancedTree {
    public static boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int lh = height(root.left);
        int rh = height(root.right);
        if (Math.abs(lh - rh) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private static int height(TreeNode node) {
        if (node == null) return 0;
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        System.out.println(isBalanced(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isBalanced(root) {
    function height(node) {
        if (!node) return 0;
        return Math.max(height(node.left), height(node.right)) + 1;
    }
    if (!root) return true;
    const lh = height(root.left);
    const rh = height(root.right);
    if (Math.abs(lh - rh) > 1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3));
console.log(isBalanced(root));

Go implementation

package main

import (
    "fmt"
    "math"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    lh := height(node.Left)
    rh := height(node.Right)
    if lh > rh {
        return lh + 1
    }
    return rh + 1
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    lh := height(root.Left)
    rh := height(root.Right)
    if math.Abs(float64(lh-rh)) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, nil}, &TreeNode{3, nil, nil}}
    fmt.Println(isBalanced(root))
}

Rust implementation

use std::cmp;

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn height(node: &Option<Box<TreeNode>>) -> i32 {
    if let Some(n) = node {
        return cmp::max(height(&n.left), height(&n.right)) + 1;
    }
    0
}

fn is_balanced(node: &Option<Box<TreeNode>>) -> bool {
    if let Some(n) = node {
        let lh = height(&n.left);
        let rh = height(&n.right);
        if (lh - rh).abs() > 1 {
            return false;
        }
        return is_balanced(&n.left) && is_balanced(&n.right);
    }
    true
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode::new(4))),
            right: None,
        })),
        right: Some(Box::new(TreeNode::new(3))),
    }));
    println!("{}", is_balanced(&root));
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun height(node: TreeNode?): Int {
    if (node == null) return 0
    return maxOf(height(node.left), height(node.right)) + 1
}

fun isBalanced(root: TreeNode?): Boolean {
    if (root == null) return true
    val lh = height(root.left)
    val rh = height(root.right)
    if (kotlin.math.abs(lh - rh) > 1) return false
    return isBalanced(root.left) && isBalanced(root.right)
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left!!.left = TreeNode(4)
    println(isBalanced(root))
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func height(_ node: TreeNode?) -> Int {
    guard let node = node else { return 0 }
    return max(height(node.left), height(node.right)) + 1
}

func isBalanced(_ root: TreeNode?) -> Bool {
    guard let root = root else { return true }
    let lh = height(root.left)
    let rh = height(root.right)
    if abs(lh - rh) > 1 { return false }
    return isBalanced(root.left) && isBalanced(root.right)
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
print(isBalanced(root))

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function height(node: TreeNode | null): number {
    if (!node) return 0;
    return Math.max(height(node.left), height(node.right)) + 1;
}

function isBalanced(root: TreeNode | null): boolean {
    if (!root) return true;
    const lh = height(root.left);
    const rh = height(root.right);
    if (Math.abs(lh - rh) > 1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3));
console.log(isBalanced(root));