forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmax_height.py
More file actions
48 lines (37 loc) · 1.11 KB
/
max_height.py
File metadata and controls
48 lines (37 loc) · 1.11 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
"""
Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth. The maximum depth is the number
of nodes along the longest path from the root down to the farthest leaf.
Reference: https://en.wikipedia.org/wiki/Binary_tree
Complexity:
Time: O(n)
Space: O(n)
"""
from __future__ import annotations
from collections import deque
from algorithms.tree.tree import TreeNode
def max_height(root: TreeNode | None) -> int:
"""Compute the maximum depth of a binary tree using iterative BFS.
Args:
root: The root of the binary tree.
Returns:
The maximum depth (number of levels) of the tree.
Examples:
>>> max_height(None)
0
"""
if root is None:
return 0
height = 0
queue: deque[TreeNode] = deque([root])
while queue:
height += 1
level: deque[TreeNode] = deque()
while queue:
node = queue.popleft()
if node.left is not None:
level.append(node.left)
if node.right is not None:
level.append(node.right)
queue = level
return height