python/data-structures/trees/lowest_common_ancestor.py at master · MaxFeussner/python · GitHub

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
108
109
110
111
112
# -*- coding: UTF-8 -*-
#
# Lowest Common Ancestor
# The All ▲lgorithms library for python
#
# Contributed by: Anish Narkhede
# Github: @anish03
#
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self,data):
        if not self.root:
            self.root = Node(data)
        else:
            self._add(data,self.root)

    def _add(self,data,node):
        if data <= node.data:
            if node.left:
                self._add(data,node.left)
            else:
                node.left = Node(data)
        else:
            if node.right:
                self._add(data,node.right)
            else:
                node.right = Node(data)

    def find(self,data):
        if self.root:
            self._find(data,self.root)
        else:
            return None

    def _find(data,node):
        if data == node.data:
            return node
        elif node.left and data <= node.data:
            return self._find(data,node.left)
        elif node.right and data > node.data:
            return self._find(data,node.right)

    def inorder(self,node):
        if node:
            self.inorder(node.left)
            print node.data
            self.inorder(node.right)

    def get_height(self,node):
        if not node:
            return 0
        else:
            i = max(self.get_height(node.left),self.get_height(node.right)) + 1
        return i

    def find_path(self,root,path,k):
        if not root:
            return False

        path.append(root.data)

        if root.data == k:
            return True

        if (root.left and self.find_path(root.left,path,k) or root.right and self.find_path(root.right,path,k)):
            return True

        path.pop()
        return False

    def Driver(self,root,n1,n2):
        path1,path2 = [],[]

        if (not self.find_path(root,path1,n1) or not self.find_path(root,path2,n2)):
            return -1

        i = 0
        while i < len(path1) and i < len(path2):
            if path1[i] != path2[i]:
                break
            i += 1
        return path1[i-1]

def main():

    B = BST()

    B.add(8)
    B.add(3)
    B.add(10)
    B.add(1)
    B.add(6)
    B.add(14)
    B.add(4)
    B.add(7)
    B.add(13)

    print B.Driver(B.root,1,6)

if __name__ == '__main__':
    main()