Determine if BinaryTree is Balanced

This post will explore the problem of checking whether a binary tree is balanced or not. A binary tree is considered to be balanced if the height difference between two subtrees is no more than 1. This definition could be different depending on use cases. We will explore two approaches to this problem. One where all nodes are visited whereas the second approach takes advantage of early termination if one subtree is unbalanced.

Brute Force

The brute force approach will recursively visit every node using in-order traversal. For each node, the algorithm will get the height of its left subtree and right subtree. The greater height of the two is incremented by one, and is returned to the parent of the current node where the process repeats. The difference is computed one last time at the root and returns false if it is larger than one.

Implementation

public static boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;

    int leftHeight = treeHeight(root.left);
    int rightHeight = treeHeight(root.right);
    return Math.abs(leftHeight - rightHeight) <= 1;
}

Helper Method

private static int treeHeight(TreeNode root) {
    if (root == null)
        return 0;

    int leftHeight = treeHeight(root.left);
    int rightHeight = treeHeight(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

Optimized

The optimized solution takes advantage of early termination in the event where one of the subtrees is detected to be unbalanced. When this occurs, the unbalanced status is passed to the parent and eventually the root. At the point where the unbalanced status is detected, there is no need to check for any other subtree.

TreeNodeAttributes Definition

public static class TreeNodeAttributes {
    boolean isBalanced;
    int height;

    public TreeNodeAttributes(isBalanced, height) {
        isBalanced = isBalanced;
        height = height;
    }
}

Implementation

public static boolean isBalanced(TreeNode root) {
    return getAttributes(root).isBalanced;
}

Helper Method

public static TreeNodeAttributes getAttributes(TreeNode root) {
    if (root == null)
        return new TreeNodeAttributes(true, 0);

    TreeNodeAttributes leftAttr = getAttributes(root.left);
    if (!leftAttr.isBalanced)
        return leftAttr;

    TreeNodeAttributes rightAttr = getAttributes(root.right);
    if (!rightAttr.isBalanced)
        return rightAttr;

    TreeNodeAttributes curAttributes = new TreeNodeAttributes();
    curAttributes.height = Math.max(leftAttr.height, rightAttr.height) + 1;
    curAttributes.isBalanced = Math.abs(leftAttr.height - rightAttr.height) <= 1;

    return curAttributes;
}

This article is my 22nd oldest. It is 174 words long, and it’s got 0 comments for now.