Skip to content

Instantly share code, notes, and snippets.

@jakemmarsh
Last active September 26, 2022 18:06
Show Gist options
  • Star 62 You must be signed in to star a gist
  • Fork 17 You must be signed in to fork a gist
  • Save jakemmarsh/8273963 to your computer and use it in GitHub Desktop.
Save jakemmarsh/8273963 to your computer and use it in GitHub Desktop.
a simple implementation of a Binary Search Tree in Python
class Node:
def __init__(self, val):
self.val = val
self.leftChild = None
self.rightChild = None
def get(self):
return self.val
def set(self, val):
self.val = val
def getChildren(self):
children = []
if(self.leftChild != None):
children.append(self.leftChild)
if(self.rightChild != None):
children.append(self.rightChild)
return children
class BST:
def __init__(self):
self.root = None
def setRoot(self, val):
self.root = Node(val)
def insert(self, val):
if(self.root is None):
self.setRoot(val)
else:
self.insertNode(self.root, val)
def insertNode(self, currentNode, val):
if(val <= currentNode.val):
if(currentNode.leftChild):
self.insertNode(currentNode.leftChild, val)
else:
currentNode.leftChild = Node(val)
elif(val > currentNode.val):
if(currentNode.rightChild):
self.insertNode(currentNode.rightChild, val)
else:
currentNode.rightChild = Node(val)
def find(self, val):
return self.findNode(self.root, val)
def findNode(self, currentNode, val):
if(currentNode is None):
return False
elif(val == currentNode.val):
return True
elif(val < currentNode.val):
return self.findNode(currentNode.leftChild, val)
else:
return self.findNode(currentNode.rightChild, val)
@Aniket2ten96
Copy link

@rakaar I think the code to find the successor_node might not yield the correct result. Suppose a bst rooted at 69, and its right side nodes are 70,82,84. Now I want to find 69's successor, according to your code i will go to right and i will find the node with maximum key and that will be the successor of 69. In the above example the maximum key is 84, which is not the successor of 69(successor of 69 is 70 in the above example) . I think to find the successor, you have to go right and find the node with minimum key value, which is in the above example 70. Correct me if I am wrong

@rakaar
Copy link

rakaar commented Sep 29, 2020

Thanks a lot @Aniket2ten96 for pointing it out
I have made the changes
You are right, it should be finding out the minimum in the subtree where self.rightNode acts as the root. Hence replaced the wrong function with find_min_in_sub_tree along with its implementation

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment