Skip to content

Instantly share code, notes, and snippets.

@timeartist
Created October 9, 2014 18:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save timeartist/288d916d5d26cef4569c to your computer and use it in GitHub Desktop.
Save timeartist/288d916d5d26cef4569c to your computer and use it in GitHub Desktop.
Pythonic Linked List
class Tree(object):
def __init__(self, root=None):
self.root = root
@classmethod
def from_string(cls, tree_string):
raise NotImplementedError
def __contains__(self, item):
if isinstance(item, Node):
return self._node_exists(item)
elif isinstance(item, Tree):
##This either will get really messy or work perfectly
return self._node_exists(item.root)
else:
return self.lookup(item)
def _node_exists(self, item):
if self.root == item:
return True
elif item.value <= self.root.value and self.root.left is not None:
return Tree(self.root.left)._node_exists(item)
elif item.value > self.root.value and self.root.right is not None:
return Tree(self.root.right)._node_exists(item)
else:
return False
def lookup(self, item):
raise NotImplementedError
def insert(self, value):
if self.root is None:
print 'Root is None - Creating Root'
self.root = Node(value)
elif value <= self.root.value and self.root.left is None:
print 'Left Node Acquired'
self.root.left = Node(value)
elif value <= self.root.value:
print 'Going to the Left Node'
Tree(self.root.left).insert(value)
elif self.root.right is None:
print 'Right Node Acquired'
self.root.right = Node(value)
else:
print 'Going to the Right Node'
Tree(self.root.right).insert(value)
class Node(object):
def __init__(self, value, left=None, right=None):
assert isinstance(left, Node) or left is None
assert isinstance(right, Node) or right is None
self.value = value
self.left = left
self.right = right
def __eq__(self, other):
if other:
return all((self.value == other.value,
self.left == other.left,
self.right == other.right))
else:
return False
if __name__ == '__main__':
n1 = Node(1, None, None)
n2 = Node(2, n1, None)
n3 = Node(2, n1, None)
#import pdb
#pdb.set_trace()
print n2 == n3
print n2 == n1
tree = Tree()
tree.insert(5)
tree.insert(7)
tree.insert(3)
tree.insert(27)
tree.insert(5)
t2 = Tree()
t2.insert(7)
t2.insert(27)
t2.insert(5)
import pdb; pdb.set_trace()
print t2 in tree
n4 = Node(27)
n5 = Node(5)
n6 = Node(7, n5, n4)
print n6 in t2
print n6 in tree
@MaxKramnik
Copy link

I would break this code apart onto 3 files :)

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