| 30 | return str(self.key) |
| 31 | |
| 32 | class BinarySearchTree: |
| 33 | def __init__(self): |
| 34 | self.root = None |
| 35 | |
| 36 | def addNode(self, treenode): |
| 37 | if self.root == None: |
| 38 | self.root = treenode |
| 39 | else: |
| 40 | buff = self.root |
| 41 | current =self.root |
| 42 | while current != None: |
| 43 | if current.key < treenode.key: |
| 44 | buff = current |
| 45 | current = current.right |
| 46 | else: |
| 47 | buff = current |
| 48 | current = current.left |
| 49 | if buff.key < treenode.key: |
| 50 | buff.right = treenode |
| 51 | treenode.p = buff |
| 52 | else: |
| 53 | buff.left = treenode |
| 54 | treenode.p = buff |
| 55 | |
| 56 | # Solution follows the chain in which p and q are on the same side. When p and q are no longer on the same side |
| 57 | # current node must be first common ancestor |