# 0110. Balanced Binary Tree

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0110-balanced-binary-tree)

Given a binary tree, determine if it is height-balanced.

For this problem, a **height-balanced binary** tree is defined as:

> binary tree in which the **left and right subtrees of *****every***** node differ in height by no more than 1**.
> {% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in the tree is in the range `[0, 5000]`.
* `-10^4 <= Node.val <= 10^4`
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Instead of calculating the height of each node's subtrees in each iteration, we **utilize DFS to return height from the bottom** **while checking whether each node's subtrees are balanced or not**.&#x20;
{% endhint %}

Since the minimum height of a tree is 0 (the root is null), we could **use '-1' to mark the node with unbalanced subtrees**.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # (base case)
        if not root: return True
        if not root.left and not root.right: return True
            
        # ==================================================
        #  Binary Tree + DFS                  (Bottom-up)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        return self.dfs(root) != -1
    
    def dfs(self, node: TreeNode) -> bool:
        if not node: return 0
        if not node.left and not node.right: return 1
        
        leftH = self.dfs(node.left)
        if leftH == -1: return -1
        
        rightH = self.dfs(node.right)
        if rightH == -1: return -1
        
        if abs(leftH - rightH) > 1: return -1
        return max(leftH, rightH) + 1
        
    '''
    def isBalanced(self, root: TreeNode) -> bool:
        # (base case)
        if not root: return True
        if not root.left and not root.right: return True
        
        # ==================================================
        #  Binary Tree                         (Top-down)  =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(n)
            
        return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 \
            and self.isBalanced(root.left) \
            and self.isBalanced(root.right)
            
    def getHeight(self, root) -> int:
        if not root: return 0
        if not root.left and not root.right: return 1
        
        return max(self.getHeight(root.left), self.getHeight(root.right)) + 1
    '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean isBalanced(TreeNode root) {
        /* base case */
        if(root == null) return true;
        if(root.left == null && root.right == null) return true;
        
        return (dfs(root) != -1) ? true : false;
    }
    
    public int dfs(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        
        int leftH = dfs(root.left);
        if(leftH == -1) return -1;
        
        int rightH = dfs(root.right);
        if(rightH == -1) return -1;
        
        if(Math.abs(leftH - rightH) > 1) return -1;
        return Math.max(leftH, rightH) + 1;
    }
}
```

{% endtab %}
{% endtabs %}