-
Notifications
You must be signed in to change notification settings - Fork 4
/
inorderSuccessorPredecessor.py
79 lines (70 loc) · 2.15 KB
/
inorderSuccessorPredecessor.py
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
from Tree.commons import insert, print_tree, is_leaf
# This function finds predecessor and successor of key in BST
# It sets pre and suc as predecessor and successor respectively
"""
1. If root is NULL
then return
2. if key is found (key == root) then
a. If its left subtree is not null
Then predecessor will be the right most
child of left subtree or left child itself.
b. If its right subtree is not null
The successor will be the left most child
of right subtree or right child itself.
return
3. If key < root
set the successor as root
search recursively into left subtree
4. Else if key > root
set the predecessor as root
search recursively into right subtree
"""
def findPreSuc(root, key):
# Base Case
if root is None:
return
# If key is present at root
if root.key == key:
# the maximum value in left subtree is predecessor
if root.left is not None:
tmp = root.left
while (tmp.right):
tmp = tmp.right
findPreSuc.pre = tmp
# the minimum value in right subtree is successor
if root.right is not None:
tmp = root.right
while (tmp.left):
tmp = tmp.left
findPreSuc.suc = tmp
return
# If key is smaller than root's key, go to left subtree
if root.key > key:
findPreSuc.suc = root
findPreSuc(root.left, key)
else: # go to right subtree
findPreSuc.pre = root
findPreSuc(root.right, key)
# Driver program to test above function
if __name__ == "__main__":
""" Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
"""
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)
findPreSuc.pre = findPreSuc.suc = None
key = 30
findPreSuc(root, key)
print ("Predecessor of {key} is {pre}, and Successor of {key} is {suc}".format(key=key,
pre=findPreSuc.pre.key,
suc=findPreSuc.suc.key))