Check if the Binary tree is height-balanced or not

Problem Overview

The problem "Balanced Binary Tree" is a common question in the area of binary trees. This problem is found on LeetCode under the topic of Binary Trees. It involves determining whether a given binary tree is balanced. A balanced binary tree is defined as a tree where the depth of the two subtrees of every node never differs by more than one.

Understanding the Problem

Given a binary tree, the task is to check if it is height-balanced. A binary tree is height-balanced if for each node, the heights of its left and right subtrees differ by at most one. This condition must hold for every node in the tree.

To solve this problem, we need to calculate the height of each subtree and ensure the difference in height for the left and right subtrees of every node is no more than one.

Key DSA Concepts and Theory

Binary Tree

A binary tree is a tree data structure where each node has at most two children referred to as the left child and the right child. Binary trees are the foundation for more sophisticated tree structures like binary search trees, AVL trees, etc.

Tree Traversal

To solve this problem, we often use depth-first search (DFS), a method for traversing or searching tree or graph data structures. The types of depth-first traversal include:

• Preorder
• Inorder
• Postorder

Height of a Tree

The height of a tree is the number of edges on the longest path from the root node to a leaf node. Calculating the height is crucial for determining if a tree is balanced.

Balanced Tree

A tree is height-balanced if the following conditions are true for every node:

1. The left and right subtrees of the node are height-balanced.
2. The height difference between the left and right subtrees of the node is at most one.

Solution Approach

To determine if a binary tree is balanced, we can use a recursive approach to calculate the height of each subtree. During the recursion, we check two conditions:

1. The left and right subtrees are balanced.
2. The height difference between the left and right subtrees at any node is at most one.

Let's go through the solution step by step.

Algorithm Steps

1. Define a recursive function height(root) that returns the height of the subtree rooted at root if it is balanced, otherwise -1.

2. Base Case: If the node is null, return 0 as height.

3. Recursive Case:

   • Recursively determine the height of the left and right subtrees.
   • If either the left or right subtree is not balanced (i.e., returns -1), the current tree is also unbalanced; return -1.
   • If the height difference between the left and right subtrees is more than one, return -1 indicating an unbalanced tree.
   • Otherwise, return the height of the current subtree, which is the maximum of the left and right subtree heights plus one.

4. In the main function isBalanced, invoke the height function. It returns true if it doesn't return -1, indicating the tree is balanced.

C++ Implementation

class Solution {
public:
    int height(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftHeight = height(root->left);
        if (leftHeight == -1) return -1;
        int rightHeight = height(root->right);
        if (rightHeight == -1) return -1;
        if (abs(leftHeight - rightHeight) > 1) return -1;
        return max(leftHeight, rightHeight) + 1;
    }
    
    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
};

Java Implementation

class Solution {
    private int height(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = height(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = height(root.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(N) where N is the number of nodes in the tree.

  The function visits every node exactly once, calculating its height and checking whether its subtree is balanced.

• Space Complexity: O(H) where H is the height of the tree.

  The space complexity is due to the stack space required during the recursive calls. In the worst case (skewed tree), the space complexity is O(N), but for a perfectly balanced tree, it is O(log N).

Common Mistakes to Avoid

• Ignoring Base Case: Forgetting to handle null nodes could lead to incorrect results or runtime errors.
• Incorrect Height Calculation: Not returning the height properly can lead to infinite recursion or incorrect balancing checks.
• Redundant Calculations: Calculating the height of a subtree multiple times can make the solution inefficient.

Similar Problems on LeetCode

• 110. Balanced Binary Tree
• 543. Diameter of Binary Tree
• 124. Binary Tree Maximum Path Sum

Additional Resources and References

• "Introduction to Algorithms" by Thomas H. Cormen, et al. - Chapters on Tree Structures
• LeetCode Discuss and Solution Pages
• Documentation on Tree Data Structures at GeeksforGeeks and other educational platforms

This comprehensive explanation should provide a clear understanding of the "Balanced Binary Tree" problem, its underlying concepts, and an efficient solution approach.