LeetCode 110: Balanced Binary Tree Solution

Master LeetCode problem 110 (Balanced Binary Tree), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

110. Balanced Binary Tree

Easy

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To determine if a binary tree is height-balanced, we can recursively check if the left and right subtrees are balanced and if the height difference between them is at most 1. We can define a helper function that calculates the height of a subtree and whether it is balanced. If any subtree is unbalanced or the height difference is more than 1, we return false.

Algorithm:

Define a helper function isBalancedHelper which takes a node as input and returns a pair (height, isBalanced).
Base case: If the node is null, return (0, true) as an empty tree is height-balanced.
Recursively call isBalancedHelper on the left and right subtrees.
Calculate the height of the current node as 1 + max(leftHeight, rightHeight).
Check if both left and right subtrees are balanced, and their height difference is at most 1.
If step 5 is true, return (currentHeight, true), else return (currentHeight, false).
In the main function, return the second element of the pair returned by isBalancedHelper.

Time Complexity:

The time complexity of this algorithm is O(n) where n is the number of nodes in the binary tree. This is because we visit each node once in the tree.

Space Complexity:

The space complexity of this algorithm is O(n) due to the recursive calls on the stack.

Solution Code

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

class Solution {
    public boolean isBalanced(TreeNode root) {
        return isBalancedHelper(root).isBalanced;
    }
    
    private class Result {
        int height;
        boolean isBalanced;
        
        Result(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }
    
    private Result isBalancedHelper(TreeNode node) {
        if (node == null) {
            return new Result(0, true);
        }
        
        Result left = isBalancedHelper(node.left);
        Result right = isBalancedHelper(node.right);
        
        int currentHeight = 1 + Math.max(left.height, right.height);
        boolean isCurrBalanced = left.isBalanced && right.isBalanced && Math.abs(left.height - right.height) <= 1;
        
        return new Result(currentHeight, isCurrBalanced);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 110 (Balanced Binary Tree)?

This page provides optimized solutions for LeetCode problem 110 (Balanced Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 110 (Balanced Binary Tree)?

The time complexity for LeetCode 110 (Balanced Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 110 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 110 in Java, C++, or Python.

Back to LeetCode Solutions