Skip to content

Instantly share code, notes, and snippets.

@AdamCanady

AdamCanady/bst.py

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.
Download ZIP

Revisions

  1. AdamCanady revised this gist Nov 11, 2014. 1 changed file with 55 additions and 13 deletions.
    68 changes: 55 additions & 13 deletions bst.py
    View file
    Original file line number Diff line number Diff line change
    @@ -5,14 +5,14 @@ def __init__(self,value):
    self.left = None

    def add(self, x):
    if x == self.value: return "Value already in tree"
    if x.value == self.value: return "Value already in tree"

    elif x < self.value:
    elif x.value < self.value:
    if self.left: return self.left.add(x)
    else: self.left = Node(x)
    elif x > self.value:
    else: self.left = x
    elif x.value > self.value:
    if self.right: return self.right.add(x)
    else: self.right = Node(x)
    else: self.right = x

    def find(self, x):
    if x == self.value: return self.value
    @@ -24,14 +24,56 @@ def find(self, x):
    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(4)
    root.add(7)
    root.add(6)
    root.add(10)
    root.add(3)
    root.add(1)

    print root.find(4)
    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)

  2. AdamCanady created this gist Nov 11, 2014.
    37 changes: 37 additions & 0 deletions bst.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,37 @@
    class Node(object):
    def __init__(self,value):
    self.value = value
    self.right = None
    self.left = None

    def add(self, x):
    if x == self.value: return "Value already in tree"

    elif x < self.value:
    if self.left: return self.left.add(x)
    else: self.left = Node(x)
    elif x > self.value:
    if self.right: return self.right.add(x)
    else: self.right = Node(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."

    if __name__ == "__main__":
    root = Node(5)
    root.add(4)
    root.add(7)
    root.add(6)
    root.add(10)
    root.add(3)
    root.add(1)

    print root.find(4)