Skip to content

Instantly share code, notes, and snippets.

@Frikster
Forked from jakemmarsh/binarySearchTree.py
Created November 15, 2017 01:02
Show Gist options
  • Save Frikster/838fedf93640876ae7016d3325edf40c to your computer and use it in GitHub Desktop.
Save Frikster/838fedf93640876ae7016d3325edf40c 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment