Skip to content

Instantly share code, notes, and snippets.

@AdamCanady
Last active August 29, 2015 14:09
Show Gist options
  • Save AdamCanady/7c5a16d9d1dd91b3a5ed to your computer and use it in GitHub Desktop.
Save AdamCanady/7c5a16d9d1dd91b3a5ed to your computer and use it in GitHub Desktop.
Quick Python BST
class Node(object):
def __init__(self,value):
self.value = value
self.right = None
self.left = None
def add(self, x):
if x.value == self.value: return "Value already in tree"
elif x.value < self.value:
if self.left: return self.left.add(x)
else: self.left = x
elif x.value > self.value:
if self.right: return self.right.add(x)
else: self.right = x
def find(self, x):
if x == self.value: return self.value
elif x < self.value:
if self.left: return self.left.find(x)
else: return "Value not in tree."
elif x > self.value:
if self.right: return self.right.find(x)
else: return "Value not in tree."
def remove(self, x):
if self.value == x: return "Cannot delete root."
elif x < self.value:
if self.left:
if self.left.value == x:
if self.left.left:
if self.left.right: self.left.left.add(self.left.right)
self.left = self.left.left
elif self.left.right:
if self.left.left: self.left.right.add(self.left.left)
self.left = self.left.right
else: return
else:
self.left.remove(x)
else:
return "Value not in tree"
elif x > self.value:
if self.right:
if self.right.value == x:
if self.right.left:
if self.right.right: self.right.left.add(self.right.right)
self.right = self.right.left
elif self.right.right:
if self.right.left: self.right.right.add(self.right.left)
self.right = self.right.right
else: return
else:
self.left.remove(x)
else:
return "Value not in tree"
if __name__ == "__main__":
root = Node(5)
root.add(Node(4))
root.add(Node(7))
root.add(Node(6))
root.add(Node(10))
root.add(Node(3))
root.add(Node(1))
root.remove(4)
root.remove(7)
print root.find(10)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment