# Balanced Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/balanced-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/balanced-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Apple](https://scaleengineer.com/companies/apple), [Capgemini](https://scaleengineer.com/companies/capgemini), [Meta](https://scaleengineer.com/companies/meta), [Uber](https://scaleengineer.com/companies/uber), [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
Given a binary tree, determine if it is **height-balanced**.

**Example 1:**

![](https://assets.glich.co/dsa/balanced-binary-tree/image0.jpg) 

**Input:** root = [3,9,20,null,null,15,7]
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/balanced-binary-tree/image1.jpg) 

**Input:** root = [1,2,2,3,3,null,null,4,4]
**Output:** false

**Example 3:**

**Input:** root = []
**Output:** true

**Constraints:**

* The number of nodes in the tree is in the range `[0, 5000]`.
* `-104 <= Node.val <= 104`

# Approaches
## Brute Force Top-Down Recursion
This approach directly translates the definition of a balanced binary tree into a recursive algorithm. For each node, it first calculates the heights of its left and right subtrees and checks if the difference is at most one. If this condition holds, it then recursively proceeds to check if the left and right subtrees are themselves balanced. This method is straightforward to understand but is inefficient because it repeatedly calculates the height of the same subtrees.
**Time:** O(N^2) in the worst case (a skewed tree). For each of the N nodes, we might traverse its entire subtree to calculate the height. For a balanced tree, the complexity is closer to O(N log N). · **Space:** O(N) in the worst case (a skewed tree) and O(log N) in the best case (a balanced tree), due to the recursion stack depth.
**Pros:** Intuitive and easy to understand as it directly models the problem statement.; Clearly separates the logic for height calculation and balance checking.
**Cons:** Highly inefficient due to redundant computations. The height of a single node might be calculated multiple times as the recursion progresses down the tree.; The time complexity is poor, especially for skewed trees, which can lead to a 'Time Limit Exceeded' error on platforms like LeetCode.
### Explanation
The core idea is to separate the problem into two distinct recursive functions: one to check for balance (`isBalanced`) and another to calculate height (`height`).

1.  **`height(TreeNode node)` function**: This helper function computes the height of a subtree rooted at `node`. It's a standard recursive height calculation. If the node is null, its height is 0. Otherwise, its height is 1 plus the maximum height of its left and right children.

2.  **`isBalanced(TreeNode root)` function**: This is the main function. For any given node, it performs three checks:
    a. It computes the heights of the left and right subtrees using the `height` helper.
    b. It checks if the absolute difference between these heights is greater than 1. If it is, the tree is not balanced, and it returns `false`.
    c. If the current node is balanced, it must also ensure that all its descendants are balanced. It does this by recursively calling `isBalanced` on its left and right children.

The entire tree is considered balanced only if the balance property holds true for every single node in the tree. The major performance issue arises from the fact that `isBalanced` calls `height`, and both functions traverse the subtrees. This means nodes are visited multiple times, leading to overlapping subproblems that are re-computed.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Helper function to calculate the height of a tree.
    private int height(TreeNode node) {
        if (node == null) {
            return 0; // Height of an empty tree is 0.
        }
        // Height is 1 + max height of left/right subtrees.
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public boolean isBalanced(TreeNode root) {
        // An empty tree is balanced.
        if (root == null) {
            return true;
        }

        // Get heights of left and right subtrees.
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // Check if the current node is balanced AND
        // if the left and right subtrees are also balanced.
        if (Math.abs(leftHeight - rightHeight) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right)) {
            return true;
        }

        return false;
    }
}
```
### Algorithm
- Define a helper function `height(node)` that recursively computes the height of a subtree. The height of a null node is 0, and the height of a non-null node is `1 + max(height(node.left), height(node.right))`.
- Define the main function `isBalanced(root)`.
- If the `root` is null, the tree is balanced, so return `true`.
- Calculate the height of the left subtree, `leftHeight = height(root.left)`.
- Calculate the height of the right subtree, `rightHeight = height(root.right)`.
- Check if the current node is balanced: `if (Math.abs(leftHeight - rightHeight) > 1)`, return `false`.
- If the current node is balanced, recursively check if its subtrees are also balanced: `return isBalanced(root.left) && isBalanced(root.right)`.

## Optimized Single-Pass Recursion (Bottom-Up)
This optimized approach combines the height calculation and balance check into a single recursive pass. It works in a bottom-up manner (similar to a post-order traversal). A helper function is designed to return the height of a subtree only if it's balanced. If an imbalance is detected at any node, it returns a special sentinel value (like -1). This sentinel value is then propagated up the recursion stack, allowing for an early exit and avoiding unnecessary computations. This reduces the time complexity from quadratic to linear.
**Time:** O(N), where N is the number of nodes in the tree, because we visit each node exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, H = N, so the complexity is O(N). For a balanced tree, it's O(log N).
**Pros:** Optimal time complexity of O(N) as each node is visited only once.; Efficiently combines height calculation and balance checking into a single pass.; Allows for early termination. As soon as an imbalance is found, it stops processing that branch and returns.
**Cons:** The logic can be slightly less direct to grasp compared to the brute-force approach because the return value is overloaded (it represents either a valid height or an error code).
### Explanation
This approach improves upon the brute-force method by eliminating redundant calculations. Instead of separating height calculation and balance checking, we merge them into a single recursive function that performs a post-order traversal of the tree.

The helper function, let's call it `checkHeight`, is designed to return two kinds of information:
1.  **The height of the subtree**: If the subtree rooted at the current node is balanced.
2.  **An error code (-1)**: If the subtree is unbalanced.

This function works as follows:
- It recursively calls itself for the left and right children.
- When the recursive calls return, it first checks if either of them returned -1. If so, it means an imbalance has already been detected in a lower part of the tree. In this case, there's no need to check the current node; we simply propagate the -1 up the call stack.
- If both subtrees are balanced (i.e., their heights are non-negative), we then check the balance condition at the current node: `Math.abs(leftHeight - rightHeight) > 1`. If this condition is met, the current node is the source of an imbalance, so we return -1.
- If the current node is also balanced, we calculate its height as `1 + Math.max(leftHeight, rightHeight)` and return it to the parent caller.

The main `isBalanced` function simply initiates the process by calling `checkHeight(root)` and checking if the final result is -1. This ensures that every node is visited only once, making the algorithm very efficient.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Helper function returns the height of a subtree if it's balanced,
    // otherwise returns -1.
    private int checkHeight(TreeNode node) {
        // Base case: An empty tree is balanced and has a height of 0.
        if (node == null) {
            return 0;
        }

        // Recursively check the left subtree.
        int leftHeight = checkHeight(node.left);
        // If the left subtree is unbalanced, propagate the imbalance signal up.
        if (leftHeight == -1) {
            return -1;
        }

        // Recursively check the right subtree.
        int rightHeight = checkHeight(node.right);
        // If the right subtree is unbalanced, propagate the imbalance signal up.
        if (rightHeight == -1) {
            return -1;
        }

        // Check if the current node is balanced.
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // Signal imbalance.
        }

        // If balanced, return the height of the current node's subtree.
        return 1 + Math.max(leftHeight, rightHeight);
    }

    public boolean isBalanced(TreeNode root) {
        // A tree is balanced if its checkHeight is not -1.
        return checkHeight(root) != -1;
    }
}
```
### Algorithm
- Define a helper function, `checkHeight(node)`, that returns the height of the subtree if it's balanced, or a sentinel value (e.g., -1) if it's not.
- **Base Case**: If `node` is null, it's a balanced subtree of height 0. Return 0.
- **Recursive Step**: 
  - Recursively call `leftHeight = checkHeight(node.left)`. If `leftHeight` is -1, an imbalance was found below. Propagate the error by immediately returning -1.
  - Recursively call `rightHeight = checkHeight(node.right)`. If `rightHeight` is -1, return -1.
  - Check the balance condition at the current node: `if (Math.abs(leftHeight - rightHeight) > 1)`, the current subtree is unbalanced, so return -1.
  - If all checks pass, the current subtree is balanced. Return its height: `1 + Math.max(leftHeight, rightHeight)`.
- The main `isBalanced(root)` function calls `checkHeight(root)` and returns `true` if the result is not -1, and `false` otherwise.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isBalanced ( TreeNode root ) { return height ( root ) >= 0 ; } private int height ( TreeNode root ) { if ( root == null ) { return 0 ; } int l = height ( root . left ); int r = height ( root . right ); if ( l == - 1 || r == - 1 || Math . abs ( l - r ) > 1 ) { return - 1 ; } return 1 + Math . max ( l , r ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isBalanced =
  function (root) {
    const height = (root) => {
      if (!root) {
        return 0;
      }
      const l = height(root.left);
      const r = height(root.right);
      if (l == -1 || r == -1 || Math.abs(l - r) > 1) {
        return -1;
      }
      return 1 + Math.max(l, r);
    };
    return height(root) >= 0;
  };

```

### CPP

```cpp
/** * 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 ) { function < int ( TreeNode * ) > height = [ & ]( TreeNode * root ) { if ( ! root ) { return 0 ; } int l = height ( root -> left ); int r = height ( root -> right ); if ( l == - 1 || r == - 1 || abs ( l - r ) > 1 ) { return - 1 ; } return 1 + max ( l , r ); }; return height ( root ) >= 0 ; } };
```

### Python

```python
# Definition for a binary tree node. # 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 : Optional [ TreeNode ]) -> bool : def height ( root ): if root is None : return 0 l , r = height ( root . left ), height ( root . right ) if l == - 1 or r == - 1 or abs ( l - r ) > 1 : return - 1 return 1 + max ( l , r ) return height ( root ) >= 0
```