Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class node:
- # constructor method
- # setting default value of left and right links to null
- def __init__(self,element,left = None,right = None):
- self.element = element
- self.left = left
- self.right = right
- # method to update left Link
- def updateLeftLink(self,link):
- self.left = link
- # method to update right link
- def updateRightLink(self,link):
- self.right = link
- # method to get the data element of the node
- def getElement(self):
- return self.element
- # method to get the Left node
- def getLeftNode(self):
- return self.left
- # method to get the right node
- def getRightNode(self):
- return self.right
- class BST:
- def __init__(self):
- self.root = None
- self.pHeight = 0
- # method returns true if the bst is empty
- def isEmpty(self):
- return self.root is None
- # method returns root of the binary search tree
- def getRoot(self):
- return self.root
- # method inserts element in the binary search tree
- def insert(self,element):
- tempNode = node(element)
- if self.getRoot() is None:
- self.root = tempNode
- else:
- inserted = False
- p = self.root
- while not inserted:
- # if new element is greater the current element then insert it to the right
- if tempNode.getElement() > p.getElement():
- # if right link of the current is null then directly insert
- if p.getRightNode() is None:
- p.updateRightLink(tempNode)
- inserted = True
- else:
- p = p.getRightNode()
- # if new element is less the current element then insert it to the left
- elif tempNode.getElement() < p.getElement():
- # if left link of the current is null then directly insert
- if p.getLeftNode() is None:
- p.updateLeftLink(tempNode)
- inserted = True
- else:
- p = p.getLeftNode()
- # method to find the common ancestor of 2 nodes
- # method assumes that both the nodes are already present in the binary tree
- def commonAncestor(self, e1, e2):
- tempNode = self.getRoot()
- parent = self.getRoot()
- found = False
- while not found:
- data = tempNode.getElement()
- # if both the elements are greater than the data then traverse right
- if data < e1 and data < e2:
- parent = tempNode
- tempNode = tempNode.getRightNode()
- # if the element are less than data traverse left
- elif data > e1 and data > e2:
- parent = tempNode
- tempNode = tempNode.getLeftNode()
- # if one of the element is equal to the data then the parent node is the required Ancestor
- elif data == e1 or data == e2:
- print("\nThe common Ancestor of " + str(e1) + " and " + str(e2) + " is " + str(parent.getElement()))
- found = True
- # if one element is greater and other is smaller then current node is the required ancestor
- else:
- print("\nThe common Ancestor of " + str(e1) + " and " + str(e2) + " is " + str(tempNode.getElement()))
- found = True
- # main function
- b1 = BST()
- b1.insert(7)
- b1.insert(29)
- b1.insert(25)
- b1.insert(36)
- b1.insert(71)
- b1.insert(24)
- b1.insert(5)
- b1.insert(9)
- b1.insert(1)
- root = b1.getRoot()
- b1.commonAncestor(6,1)
- b1.commonAncestor(1,9)
- b1.commonAncestor(9,36)
Add Comment
Please, Sign In to add comment