110. Balanced Binary Tree

📝 Problem Details

• Title: 110. Balanced Binary Tree
• Link: https://leetcode.com/problems/balanced-binary-tree/
• Difficulty: Easy
• Tags/Categories: Trees

💭What Were My Initial Thoughts?

- height of a node is max(leftHeight - rightHeight) + 1
- a tree is balanced if:
	- both subtrees are balanced
	- the height difference between left and right subtrees is at most 1
- instead of of checking the minimum depth, we should check the height difference at each node recursively 

💡 Explanation of Solution

- perform DFS (bottom-up) to determine balance
	- allows us to return the height while simultaneously checking balance
	- compute left height and right height for each node 
	- if any subtree is unbalanced, return -1 to indicate imbalance
	- if abs(leftHeight - rightHeight) > 1, return -1 (imbalanced)
	- otherwise, return the height of the current node (max(leftHeight, rightHeight) + 1)

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(log n) to O(n) depending on balance of the tree due to use of recursive call stack 

💻 Implementation of Solution

class Solution {
private:
    int dfsHeight(TreeNode* root) {
        if(root == nullptr) return 0; // base case: null node has height of 0
 
        int leftHeight = dfsHeight(root->left);
        if(leftHeight == -1) return -1; // propagate imbalance up the call stack
 
        int rightHeight = dfsHeight(root->right);
        if(rightHeight == -1) return -1;
 
        // check balance condition
        if(abs(leftHeight - rightHeight) >  1) return -1;
 
        return max(leftHeight, rightHeight) + 1; // return height
    }
 
public:
    bool isBalanced(TreeNode* root) {
        return dfsHeight(root) != -1;
    }
};