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)
@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