forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathis_balanced.py
More file actions
33 lines (28 loc) · 722 Bytes
/
is_balanced.py
File metadata and controls
33 lines (28 loc) · 722 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def is_balanced(root):
"""
O(N) solution
"""
return -1 != get_depth(root)
def get_depth(root):
"""
return 0 if unbalanced else depth + 1
"""
if not root:
return 0
left = get_depth(root.left)
right = get_depth(root.right)
if abs(left-right) > 1:
return -1
return 1 + max(left, right)
################################
def is_balanced(root):
"""
O(N^2) solution
"""
left = max_height(root.left)
right = max_height(root.right)
return abs(left-right) <= 1 and is_balanced(root.left) and is_balanced(root.right)
def max_height(root):
if not root:
return 0
return max(max_height(root.left), max_height(root.right)) + 1