【Video】3 points to solve this question
IntuitionSolution Video⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️■ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmatio
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

---

# Solution Video

https://youtu.be/65AwU6qquPk

### ⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️

**■ Subscribe URL**
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

Subscribers: 16,277
Thank you for your support!

---


# Approach

First of all, what is the points to solve this question?


---

 - How do you handle null?
 - How do you calculate height difference?
 - What do you keep for the next recursive process?
---

### How do you handle null?

Simply, we consider null as balanced. `null` is nothing at current position and both side. **That means the fact that nothing exists makes the left and right sides balanced.**


### How do you calculate height difference?

The description says "A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one."

Since we need to know the height difference, we have to subtract the left and right heights.

For example, 
```
left height is 5.
right height is 4.

```
In this case, difference is `1`. But one problem here is that if we calculate 
```
left height - right height
= 5 - 4
= 1(= true)
```
We will get `1`, but these is a case where left height is `4` and right height is `5`. **left height is not always higher than right height.** In that case,

```
left height - right height
= 4 - 5
= -1
```
Difference should be `1` for both cases. You could handle this with an if statement, but it might not be the most elegant solution. There’s probably a simpler and smarter way—any ideas?

My answer is to use absolute values, so that we can handle `1` and `-1` as `1`.
```
abs(left height - right height)
= abs(4 - 5)
= 1
```
### What do you keep for the next recursive process?

I think we need to pass two pieces of data to the next recursive call. Any ideas?  

One is a boolean value to track whether the tree has remained balanced from the leaf nodes up to this point, since every part of the tree must be balanced.  

The other is the height of the current subtree, including the current node, which is needed to check if the left and right sides are balanced at this level.  

Using these two in the next recursive call should allow us to determine whether the tree is balanced.


---

https://youtu.be/K3MES6kEIMA

---

# Complexity
- Time complexity: $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n)$$
In the worst case (a skewed tree), the recursion depth is $$O(n)$$.

# Code

```python []
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(root):
            if not root:
                return [True, 0]
            
            left_balanced, left_height = dfs(root.left)
            right_balanced, right_height = dfs(root.right)
            
            is_balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
            
            return [is_balanced, 1 + max(left_height, right_height)]
        
        return dfs(root)[0]
```
```javascript []
var isBalanced = function(root) {
    function dfs(node) {
        if (!node) return [true, 0];
        
        const [leftBalanced, leftHeight] = dfs(node.left);
        const [rightBalanced, rightHeight] = dfs(node.right);
        
        const isBalanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1;
        
        return [isBalanced, 1 + Math.max(leftHeight, rightHeight)];
    }
    
    return dfs(root)[0];    
};
```
```java []
class Solution {
    public boolean isBalanced(TreeNode root) {
        int[] result = dfs(root);
        return result[0] == 1;        
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{1, 0}; // {isBalanced (1 for true, 0 for false), height}
        
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        
        boolean isBalanced = left[0] == 1 && right[0] == 1 && Math.abs(left[1] - right[1]) <= 1;
        
        return new int[]{isBalanced ? 1 : 0, 1 + Math.max(left[1], right[1])};
    }    
}
```
```C++ []
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return dfs(root).first;        
    }

private:
    pair<bool, int> dfs(TreeNode* node) {
        if (!node) return {true, 0};
        
        auto [leftBalanced, leftHeight] = dfs(node->left);
        auto [rightBalanced, rightHeight] = dfs(node->right);
        
        bool isBalanced = leftBalanced && rightBalanced && abs(leftHeight - rightHeight) <= 1;
        
        return {isBalanced, 1 + max(leftHeight, rightHeight)};
    }    
};
```

---

Thank you for reading my post.
⭐️ Please upvote it and don't forget to subscribe to my channel!

■ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

https://youtu.be/pCc4kR-TdYs
['Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']