-
Notifications
You must be signed in to change notification settings - Fork 0
/
LCA.py
68 lines (51 loc) · 1.37 KB
/
LCA.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
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
path = {}
a = []
parent = None
def findRoots(root, n, depth=0):
if root is None:
return
global parent
global path
# print('Node: ', root.key, ' depth: ', depth, ' parent: ', parent)
if root.key not in path:
path[root.key] = [parent, depth]
if root.key == n:
return path
depth += 1
parent = root.key
findRoots(root.left if root.left else None, n, depth)
parent = root.key
findRoots(root.right if root.right else None, n, depth)
return path
def findLCA(root, a, b):
findRoots(root, a)
findRoots(root, b)
return lca(a, b)
def lca(a, b):
if path[a][0] is None and path[b][0] is None:
return None
elif path[a][0]:
return path[a][0]
elif path[b][0]:
return path[b][0]
elif path[a][0] == path[b][0]:
print("Found LCA: ", path[b][0])
return path[b][0]
else:
lca(path[a][0], path[b][0])
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("LCA(4, 5) = ", (findLCA(root, 4, 5,)))
print("LCA(4, 6) = ", (findLCA(root, 4, 6)))
print("LCA(3, 4) = ", (findLCA(root, 3, 4)))
print("LCA(4, 7) = ", (findLCA(root, 4, 7)))