# Tree - Balanced Binary Tree

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

Start from leaf - PostOrder dfs()

## Problem

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

A

height-balancedbinary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

**Example 1:**

1
2

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

**Example 2:**

1
2

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

**Example 3:**

1
2

Input: root = []
Output: true

## Solution

We need to use **Bottom Up** (Post Order) for solving this. Just like any Tree problem we will be using **DFS** approach here. Lets visualize the approach first.

First step is to define the base condition. We will return if the current node is balanced and whats the current height. The `None`

nodes are always balanced and height of them are always `0`

. So our base condition always returns `[True, 0]`

.

1
2

if not root:
return [True,0]

Since we will be staring from bottom-up we need to get to the base conditio. So lets run `dfs()`

on both the `left`

and `right`

nodes.

1
2

left = dfs(root.left)
right = dfs(root.right)

Next, we need to find out if the current `left`

and `right`

nodes are balanced or not. First check if any of the child node are balanced or not & then compare the height of the current `left`

and `right`

nodes.

1

balaned = left[0] and right[0] and abs(left[1]-right[1]) <=1

Finally, return the array by calculating the max height.

1

return [balaned, 1+max(left[1],right[1])]

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def isBalanced(root: TreeNode) -> bool:
def dfs(root):
if not root:
return [True, 0]
left = dfs(root.left)
right = dfs(root.right)
balanced = left[0] and right[0] and (abs(left[1]-right[1]) <= 1)
return [balanced, 1+max(left[1], right[1])]
return dfs(root)[0]