# 110. Balanced Binary Tree — LeetCode (Python)

I got you!

# Problem:

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

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

a binary tree in which the left and right subtrees ofeverynode differ in height by no more than 1.

**Example 1:**

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

**Output:** true

**Example 2:**

**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`

# Solution:

## Explanation —

We can use a depth-first search (DFS) traversal algorithm to solve this problem recursively.

We use a global variable ** ans,** to keep track of our balanced status. It is initially set to

*True.*

We are given that —

a binary tree in which the left and right subtrees of

everynode differ in height by no more than 1.

Therefore, we traverse all nodes in the tree and find the heights of every node’s *left* and *right* subtrees.

If the absolute difference between them is greater than one, we can say that our binary tree is not balanced. So , we update ** ans** to

*False.*

Finally, we return *ans.*

## Time and Space Complexity —

Since we are visiting all nodes in the tree a constant number of times, we can say that our algorithm requires a linear amount of time to run.

Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.

Thus, if *n* is the number of nodes in the given binary tree,

Time Complexity: O(n)

Space Complexity: O(n)