Leetcode 110. Balanced Binary Tree

Balanced Binary Tree

Leetcode 110. Balanced Binary Tree : Given a binary tree, determine if it is height-balanced.

DFS Recursive Method Approach 1:


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

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // Check if the current node is balanced and recursively check its subtrees
        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int height(TreeNode node) {
        if (node == null)
            return 0;

        // Calculate height of the node's left and right subtrees recursively
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        // Return the height of the node
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

See Video lecture

Leetcode 110. Balanced Binary Tree

Introduction

The "Balanced Binary Tree" problem is to determine if a given binary tree is balanced. A binary tree is considered balanced if for every node in the tree, the difference in heights between its left and right subtrees is no more than one.

This problem is important because balancing ensures that tree operations like insertion, deletion, and searching remain efficient with a time complexity of O(log n) in the best case, where n is the number of nodes in the tree.

Problem Statement

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as:

The left and right subtrees of every node differ in height by no more than 1.
The tree is balanced if the condition holds for every node in the tree.

Return true if the tree is balanced, and false otherwise.

        class TreeNode:
            def __init__(self, val=0, left=None, right=None):
                self.val = val
                self.left = left
                self.right = right

The tree node structure is defined as above, and you need to implement a function to check if the tree is balanced.

Approach

To solve the problem, we can use a recursive depth-first approach. The idea is to check the balance condition at each node while simultaneously calculating the height of the left and right subtrees. If, at any point, the difference in height exceeds 1, we can immediately return false, indicating that the tree is not balanced.

The main steps in the solution are:

Recursively calculate the height of the left and right subtrees of each node.
If the difference in height between the left and right subtrees of any node is greater than 1, return false.
If all nodes satisfy the balance condition, return true.

This approach allows us to check for both the balance and the height of the tree simultaneously in a single traversal.

Algorithm

The algorithm can be broken down into the following steps:

Define a helper function to compute the height of the tree while checking if the tree is balanced.
At each node, compute the height of the left and right subtrees.
Check if the difference in height between the left and right subtrees is greater than 1.
If at any point the difference exceeds 1, return false. Otherwise, continue the recursion.
Return true if the tree is balanced, and false otherwise.

This approach ensures that we only traverse each node once, and each node is checked for balance during the traversal.

Example

Consider the following binary tree:

The tree is balanced because the height difference between the left and right subtrees of every node is no more than 1.

Now, consider the following unbalanced binary tree:

This tree is unbalanced because the left subtree of node 1 has a height of 2, while the right subtree has a height of 1. The difference in height is greater than 1, so the tree is unbalanced.

Code Implementation

Below is the Python code to check if a binary tree is balanced:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isBalanced(self, root):
        # Helper function to check the height of the tree and balance condition
        def check_balance(node):
            # If node is null, return 0 (height of a null node is 0)
            if not node:
                return 0
            
            # Recursively get the height of the left subtree
            left_height = check_balance(node.left)
            if left_height == -1:  # If left subtree is unbalanced, propagate the unbalanced state
                return -1
            
            # Recursively get the height of the right subtree
            right_height = check_balance(node.right)
            if right_height == -1:  # If right subtree is unbalanced, propagate the unbalanced state
                return -1
            
            # If the current node is unbalanced, return -1
            if abs(left_height - right_height) > 1:
                return -1
            
            # Return the height of the current node (max height of left or right subtree + 1)
            return max(left_height, right_height) + 1
        
        # Start the recursive balance check
        return check_balance(root) != -1

In this code: - The `check_balance` function recursively checks the height of each node and verifies the balance condition. - If at any point the tree is unbalanced (i.e., the height difference between the left and right subtrees is greater than 1), the function returns -1 to indicate the unbalanced state. - The `isBalanced` function calls the helper function and returns true if the tree is balanced, and false otherwise.

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the traversal to calculate its height and check for balance.

The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case, for an unbalanced tree, the height will be O(n), resulting in a space complexity of O(n). For a balanced tree, the height will be O(log n), so the space complexity will be O(log n).

Optimized Approach

The current approach is already optimal in terms of time complexity, as we only traverse each node once. The space complexity is determined by the recursion stack, which is determined by the height of the tree.

There is no further optimization for time complexity, but if necessary, an iterative approach could be explored to reduce the recursion overhead in cases where the tree is deep and unbalanced.

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the binary tree. The space complexity is O(h), where h is the height of the tree, which can be O(n) in the worst case (for an unbalanced tree) and O(log n) for a balanced tree.

Conclusion

The "Balanced Binary Tree" problem involves checking if a binary tree is balanced, meaning that for every node, the difference in heights between its left and right subtrees is no more than 1. The solution uses a recursive approach to check the balance and compute the height of each node. The time complexity of the solution is O(n), where n is the number of nodes in the tree, and the space complexity is O(h), where h is the height of the tree.