> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/tree-traversal/check-balanced-tree.md).

# Check balanced tree

**Problem:** check if given tree is balanced

Balanced Definition:

1. Height of left and right subtree <= 1
2. Right and left subtree also balanced

**Solution:** Recursive post order traversal

**Base Case:** if root == null return true

**Recursive rule:**&#x20;

1. If left or right height differ by more than 1, return false
2. check left && right

**Implementation:**

```
public boolean balanceCheck(TreeNode root){
    if (root == null) return true;
    
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    
    if (Math.abs(leftHeight - rightHeight) > 1) return false;
    
    return balanceCheck(root.left) && balancedCheck(root.right);
}
```

**Time complexity:**&#x20;

Every node visited, each node checks height of left and right

Each level O(N) \* Log(N) levels

O(N LogN)

**Space Complexity:**

No new struct generated

O(1)