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
50 lines (36 loc) · 1.12 KB
/
is_balanced.py
File metadata and controls
50 lines (36 loc) · 1.12 KB
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
"""
Balanced Binary Tree
Determines whether a binary tree is height-balanced, meaning the depth of the
left and right subtrees of every node differ by at most one.
Reference: https://en.wikipedia.org/wiki/AVL_tree
Complexity:
Time: O(n)
Space: O(n) due to recursion stack
"""
from __future__ import annotations
from algorithms.tree.tree import TreeNode
def is_balanced(root: TreeNode | None) -> bool:
"""Check whether a binary tree is height-balanced.
Args:
root: The root of the binary tree.
Returns:
True if the tree is balanced, False otherwise.
Examples:
>>> is_balanced(None)
True
"""
return _get_depth(root) != -1
def _get_depth(root: TreeNode | None) -> int:
"""Compute the depth of a tree, returning -1 if unbalanced.
Args:
root: The root of the subtree.
Returns:
The depth of the subtree, or -1 if it is unbalanced.
"""
if root is None:
return 0
left = _get_depth(root.left)
right = _get_depth(root.right)
if abs(left - right) > 1 or -1 in [left, right]:
return -1
return 1 + max(left, right)