Python/data_structures/binary_tree/floor_and_ceiling.py at master · TheAlgorithms/Python · GitHub

Name: Python/data_structures/binary_tree/floor_and_ceiling.py at master · TheAlgorithms/Python · GitHub
Rating: 4.4 (8055 reviews)
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
"""
In a binary search tree (BST):
* The floor of key 'k' is the maximum value that is smaller than or equal to 'k'.
* The ceiling of key 'k' is the minimum value that is greater than or equal to 'k'.

Reference:
https://bit.ly/46uB0a2

Author : Arunkumar
Date : 14th October 2023
"""

from __future__ importannotations

fromcollections.abcimportIterator
fromdataclassesimportdataclass


@dataclass
classNode:
key: int
left: Node|None=None
right: Node|None=None

def__iter__(self) ->Iterator[int]:
ifself.left:
yieldfromself.left
yieldself.key
ifself.right:
yieldfromself.right

def__len__(self) ->int:
returnsum(1for_inself)


deffloor_ceiling(root: Node|None, key: int) ->tuple[int|None, int|None]:
"""
 Find the floor and ceiling values for a given key in a Binary Search Tree (BST).

 Args:
 root: The root of the binary search tree.
 key: The key for which to find the floor and ceiling.

 Returns:
 A tuple containing the floor and ceiling values, respectively.

 Examples:
 >>> root = Node(10)
 >>> root.left = Node(5)
 >>> root.right = Node(20)
 >>> root.left.left = Node(3)
 >>> root.left.right = Node(7)
 >>> root.right.left = Node(15)
 >>> root.right.right = Node(25)
 >>> tuple(root)
 (3, 5, 7, 10, 15, 20, 25)
 >>> floor_ceiling(root, 8)
 (7, 10)
 >>> floor_ceiling(root, 14)
 (10, 15)
 >>> floor_ceiling(root, -1)
 (None, 3)
 >>> floor_ceiling(root, 30)
 (25, None)
 """
floor_val=None
ceiling_val=None

whileroot:
ifroot.key==key:
floor_val=root.key
ceiling_val=root.key
break

ifkey<root.key:
ceiling_val=root.key
root=root.left
else:
floor_val=root.key
root=root.right

returnfloor_val, ceiling_val


if__name__=="__main__":
importdoctest

doctest.testmod()