-
Notifications
You must be signed in to change notification settings - Fork 4
/
pathToTarget.py
107 lines (89 loc) · 2.92 KB
/
pathToTarget.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
from Tree.commons import insert, print_tree, is_leaf
# Time complexity: O(n)
def path_to_target_util_v1(root, target_key, path=[]):
if root == None:
return False
if root.key == target_key:
path.append(root.key)
return True
lpath = path_to_target_util_v1(root.left, target_key, path)
rpath = path_to_target_util_v1(root.right, target_key, path)
if lpath or rpath:
path.append(root.key)
return lpath or rpath
def path_to_target_v1(root, target_key):
path = []
path_to_target_util_v1(root, target_key, path)
return path[::-1]
# Time complexity: O(log(n))
def path_to_target_v2(root, target_key, path=[]):
if root == None:
return False
path.append(root.key)
if root.key == target_key:
return True
elif target_key < root.key:
return path_to_target_v2(root.left, target_key, path)
elif target_key > root.key:
return path_to_target_v2(root.right, target_key, path)
path_v3 = []
def path_to_target_v3(root, target_key):
# global path_v3
if root is None:
return None
if root.key == target_key:
path_v3.append(root.key)
return root
lpath = path_to_target_v3(root.left, target_key)
if lpath is not None:
path_v3.append(root.key)
return root
rpath = path_to_target_v3(root.right, target_key)
if rpath is not None:
path_v3.append(root.key)
return root
return None
# Driver program to test above function
if __name__ == "__main__":
""" Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80
/ \
15 25
"""
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 15)
insert(root, 25)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)
target = 40
print ("\n----------------- USING V1 -----------------\n")
path = path_to_target_v1(root, target)
if len(path) > 0:
print ("Path from root {root} to node {target} is - {path}"\
.format(root=root.key, target=target, path=path))
else:
print ("Target key {target} not found".format(target=target))
print ("\n----------------- USING V2 -----------------\n")
path = []
is_path_exists = path_to_target_v2(root, target, path)
if is_path_exists:
print ("Path from root {root} to node {target} is - {path}"\
.format(root=root.key, target=target, path=path))
else:
print ("Target key {target} not found".format(target=target))
print ("\n----------------- USING V3 -----------------\n")
path_to_target_v3(root, target)
if len(path_v3) > 0:
print("Path from root {root} to node {target} is - {path}" \
.format(root=root.key, target=target, path=path_v3[::-1]))
else:
print ("Target key {target} not found".format(target=target))