NUHMAN.com

Introduction

LeetCode 110: Balanced Binary Tree asks us to determine whether a given binary tree is height-balanced. A height-balanced binary tree is defined as a tree where the depths of the two subtrees of every node differ by no more than one. The problem is essentially about verifying whether a binary tree is balanced based on its structure.

The key to solving this problem efficiently lies in computing the height of the tree and ensuring that the height difference between the left and right subtrees of every node is within the allowed limit of 1.

Problem Statement

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the difference between the heights of the left and right subtrees of every node is no more than one.

Example:

go

Input: root = [3,9,20,null,null,15,7]
Output: true

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Approach:

Using Depth-First Search (DFS)

The solution to this problem can be efficiently obtained using a Depth-First Search (DFS) traversal to compute the height of the tree at each node and simultaneously check the balance condition:

1. Base Case:

• If a node is nil, it is considered balanced and has a height of 0.

1. Recursive Case:

• For each node, recursively calculate the height of its left and right subtrees.
• If the difference in heights of the left and right subtrees exceeds 1 at any point, return false because the tree is not balanced.
• If the tree is balanced at the current node, compute the height of the node as 1 + max(left height, right height).

1. Optimizations:

• We can prune the search early by returning -1 as soon as an imbalance is detected. This allows us to avoid unnecessary computations.

By performing the DFS traversal and checking the balance condition at each node, we can determine whether the tree is balanced.

Go Implementation

Solution Using DFS

go

package main

// TreeNode represents a node in the binary tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// isBalanced checks whether the binary tree is height-balanced.
func isBalanced(root *TreeNode) bool {
    // Helper function to get the height of the tree and check balance.
    var checkBalance func(node *TreeNode) int
    checkBalance = func(node *TreeNode) int {
        // Base case: if the node is nil, it is balanced and has height 0.
        if node == nil {
            return 0
        }

        // Check the left and right subtree heights.
        leftHeight := checkBalance(node.Left)
        if leftHeight == -1 {
            return -1 // Return -1 if the left subtree is not balanced.
        }

        rightHeight := checkBalance(node.Right)
        if rightHeight == -1 {
            return -1 // Return -1 if the right subtree is not balanced.
        }

        // If the height difference between the left and right subtrees is greater than 1, return -1.
        if abs(leftHeight-rightHeight) > 1 {
            return -1
        }

        // Return the height of the current node: 1 + max(left height, right height).
        return 1 + max(leftHeight, rightHeight)
    }

    // Call the helper function on the root and check if the tree is balanced.
    return checkBalance(root) != -1
}

// max returns the maximum of two integers.
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// abs returns the absolute value of an integer.
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Explanation:

1. TreeNode Structure:

• The TreeNode struct represents a node in the binary tree. It has a value (Val) and pointers to its left and right children (Left and Right).

1. isBalanced Function:

• This is the main function that determines whether the tree is balanced. It calls the helper function checkBalance which performs the DFS traversal and checks for balance.
• If at any point, the height difference between the left and right subtrees is greater than 1, the function returns false.

1. checkBalance Helper Function:

• This function calculates the height of a subtree and checks whether it is balanced.
• It recursively calculates the height of the left and right subtrees.
• If either subtree is unbalanced (i.e., returns -1), the function immediately propagates -1 upwards to indicate the imbalance.
• If the node is balanced, the function returns the height of the subtree rooted at that node.

1. max and abs Functions:

• max returns the maximum of two integers, which is used to compute the height of the current node.
• abs returns the absolute value of an integer to check the height difference.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Where:

• n is the number of nodes in the binary tree.
• h is the height of the binary tree.

Time Complexity:

• The time complexity is O(n) because we perform a DFS traversal of the entire tree, visiting each node exactly once.

Space Complexity:

• The space complexity is O(h) where h is the height of the tree. This is the space required for the recursion stack. In the worst case (when the tree is unbalanced and resembles a linked list), the space complexity is O(n). In the best case (when the tree is perfectly balanced), the space complexity is O(log n).

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: true
• Explanation: An empty tree is considered balanced by definition.

1. Single Node Tree:

• Input: root = [1]
• Output: true
• Explanation: A tree with one node is balanced.

1. Imbalanced Tree:

• Input: root = [1,2,2,3,3,null,null,4,4]
• Output: false
• Explanation: The tree is imbalanced because the left subtree of node 2 has a depth of 3 and the right subtree has a depth of 1, violating the balance condition.

1. Balanced Tree:

• Input: root = [3,9,20,null,null,15,7]
• Output: true
• Explanation: The tree is balanced since the difference in height between the left and right subtrees of each node is no more than 1.

Conclusion

LeetCode 110: Balanced Binary Tree is a problem that tests your understanding of binary tree traversal and balance conditions. By using DFS to compute the height of subtrees and checking the balance condition at each node, we can efficiently determine whether a binary tree is height-balanced. The solution ensures a time complexity of O(n), where n is the number of nodes in the tree, and space complexity of O(h), where h is the height of the tree.