Solution For Balanced Binary Tree

The Balanced Binary Tree problem on LeetCode can be found at https://leetcode.com/problems/balanced-binary-tree/.

The problem statement is as follows:
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

To solve this problem, we need to recursively check the height of the left and right subtrees of each node and compare them. If the difference between the heights is greater than 1, then the tree is not height-balanced.

We will implement a recursive solution to check the height of the tree and compare the heights of the left and right subtrees.

First, we will define a helper function to calculate the height of a given node:
int height(TreeNode* node) {
if (!node) {
return 0;
}
return 1 + max(height(node->left), height(node->right));
}

The height function takes a node as input and recursively calculates the height of the subtree rooted at that node. If the node is NULL, the function returns 0. Otherwise, it returns 1 plus the maximum height of the left and right subtrees.

Next, we will define the main function isBalanced which takes the root of the binary tree as input:
bool isBalanced(TreeNode* root) {
if (!root) {
return true;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}

The isBalanced function first checks if the root is NULL. If it is NULL, the function returns true because an empty tree is always height-balanced.

If the root is not NULL, we calculate the height of the left and right subtrees using the height function. We then check if the absolute difference between the heights is greater than 1. If it is, the function returns false because the tree is not height-balanced.

If the difference between the heights is less than or equal to 1, we recursively call isBalanced on the left and right subtrees. If both subtrees are height-balanced, the function returns true. Otherwise, if either subtree is not height-balanced, the function returns false.

The time complexity of this solution is O(n^2) in the worst case because we may need to calculate the height of each node in the binary tree, and each height calculation takes O(n) time in the worst case. The space complexity is O(n) because we use recursion to traverse the binary tree and store the maximum height of each subtree on the call stack.

However, we can optimize the time complexity to O(n) by calculating the height of each node only once. We can do this by modifying the height function to check if the subtree rooted at a node is height-balanced and return the height of the subtree at the same time. This avoids redundant calculations of the subtree height.

Here is the optimized height function:
int height(TreeNode* node, bool& balanced) {
if (!node) {
return 0;
}
int leftHeight = height(node->left, balanced);
int rightHeight = height(node->right, balanced);
if (abs(leftHeight - rightHeight) > 1) {
balanced = false;
}
return 1 + max(leftHeight, rightHeight);
}

We add a boolean parameter balanced to the height function to indicate if the subtree rooted at a node is height-balanced. If the difference between the heights of the left and right subtrees is greater than 1, we set balanced to false.

Here is the modified isBalanced function using the optimized height function:
bool isBalanced(TreeNode* root) {
bool balanced = true;
height(root, balanced);
return balanced;
}

The isBalanced function initializes balanced to true and calls the height function on the root. The function then returns the value of balanced.

With the optimized height function, the time complexity of this solution is O(n) in the worst case, and the space complexity is O(n) due to the recursion.

Step by Step Implementation For Balanced Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        //check if tree is empty
        if(root == null)
            return true;
        
        //get the height of left and right sub-trees
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        //check if the difference in height of left and right sub-trees is not more than 1 and 
        //that the left and right sub-trees are balanced
        return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left) && isBalanced(root.right);
    }
    
    //function to get the height of a tree
    public int getHeight(TreeNode root){
        //check if tree is empty
        if(root == null)
            return 0;
        
        //if tree is not empty, return the height of the tree by recursively 
        //calculating the height of the left and right sub-trees
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
}

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: TreeNode) -> bool:
        # A tree is balanced if the difference in the depths
        # of its left and right subtrees is not more than 1.
        # An empty tree is balanced.
        
        # Return True if the tree is balanced, False otherwise.
        if not root:
            return True
        return (abs(self.depth(root.left) - self.depth(root.right)) <= 1 
                and self.isBalanced(root.left) 
                and self.isBalanced(root.right))
        
    def depth(self, root):
        # Return the depth of the tree.
        if not root:
            return 0
        return 1 + max(self.depth(root.left), self.depth(root.right))

var isBalanced = function(root) {
    if (!root) return true;
    
    function getHeight(node) {
        if (!node) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
    
    return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        // An empty tree is balanced by definition
        if (root == nullptr) {
            return true;
        }
        
        // Check if the subtrees are balanced, and if the
        // difference in their heights is no more than 1.
        return isBalanced(root->left) &&
               isBalanced(root->right) &&
               abs(getHeight(root->left) - getHeight(root->right)) <= 1;
    }
    
    int getHeight(TreeNode* root) {
        // An empty tree has height -1
        if (root == nullptr) {
            return -1;
        }
        
        // The height of a tree is the maximum height of its subtrees
        // plus 1 (for the root node).
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsBalanced(TreeNode root) {
        // Base case
        if (root == null) {
            return true;
        }
        
        // Recursive case
        int heightDiff = GetHeight(root.left) - GetHeight(root.right);
        if (Math.Abs(heightDiff) > 1) {
            return false;
        } else {
            return IsBalanced(root.left) && IsBalanced(root.right);
        }
    }
    
    private int GetHeight(TreeNode root) {
        // Base case
        if (root == null) {
            return 0;
        }
        
        // Recursive case
        return 1 + Math.Max(GetHeight(root.left), GetHeight(root.right));
    }
}