This notebook was prepared by Marco Guajardo. Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).
Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.
In order
Post order
Pre order
In [7]:
%%writefile binary_search_tree.py
class Node (object):
def __init__ (self, data):
self.data = data
self.rightChild = None
self.leftChild = None
class BinaryTree (object):
def __init__ (self):
self.root = None
def insert (self, newData):
leaf = Node(newData)
if self.root is None:
self.root = leaf
else:
current = self.root
parent = self.root
while current is not None:
parent = current
if newData < current.data:
current = current.leftChild
else:
current = current.rightChild
if newData < parent.data:
parent.leftChild = leaf
else:
parent.rightChild = leaf
# returns false if the item to be deleted is not on the tree
def delete (self, data):
current = self.root
parent = self.root
isLeft = False
if current is None:
return False
while current is not None and current.data is not data:
parent = current
if data < current.data:
current = current.leftChild
isLeft = True
else:
current = current.rightChild
isLeft = False
if current is None:
return False
if current.leftChild is None and current.rightChild is None:
if current is self.root:
self.root = None
elif isLeft:
parent.leftChild = None
else:
parent.rightChild = None
elif current.rightChild is None:
if current is self.root:
self.root = current.leftChild
elif isLeft:
parent.leftChild = current.leftChild
else:
parent.rightChild = current.leftChild
elif current.rightChild is None:
if current is self.root:
self.root = current.rightChild
elif isLeft:
parent.lChild = current.rightChild
else:
parent.rightChild = current.rightChild
else:
succesor = current.rightChild
succesorParent = current
while succesor.leftChild is not None:
succesorParent = succesor
succesor = succesor.leftChild
if current is self.root:
self.root = succesor
elif isLeft:
parent.leftChild = succesor
else:
parent.rightChild = succesor
succesor.leftChild = current.leftChild
if succesor is not current.rightChild:
succesorParent.leftChild = succesor.rightChild
succesor.rightChild = current.rightChild
return True
def minNode (self):
current = self.root
while current.leftChild is not None:
current = current.leftChild
return current.data
def maxNode (self):
current = self.root
while current.rightChild is not None:
current = current.rightChild
return current.data
def printPostOrder (self):
global postOrder
postOrder = []
def PostOrder(node):
if node is not None:
PostOrder(node.leftChild)
PostOrder(node.rightChild)
postOrder.append(node.data)
PostOrder(self.root)
return postOrder
def printInOrder (self):
global inOrder
inOrder = []
def InOrder (node):
if node is not None:
InOrder(node.leftChild)
inOrder.append(node.data)
InOrder(node.rightChild)
InOrder(self.root)
return inOrder
def printPreOrder (self):
global preOrder
preOrder = []
def PreOrder (node):
if node is not None:
preOrder.append(node.data)
PreOrder(node.leftChild)
PreOrder(node.rightChild)
PreOrder(self.root)
return preOrder
def treeIsEmpty (self):
return self.root is None
In [8]:
%run binary_search_tree.py
In [9]:
%%writefile test_binary_search_tree.py
from nose.tools import assert_equal
class TestBinaryTree(object):
def test_insert_traversals (self):
myTree = BinaryTree()
myTree2 = BinaryTree()
for num in [50, 30, 70, 10, 40, 60, 80, 7, 25, 38]:
myTree.insert(num)
[myTree2.insert(num) for num in range (1, 100, 10)]
print("Test: insert checking with in order traversal")
expectVal = [7, 10, 25, 30, 38, 40, 50, 60, 70, 80]
assert_equal(myTree.printInOrder(), expectVal)
expectVal = [1, 11, 21, 31, 41, 51, 61, 71, 81, 91]
assert_equal(myTree2.printInOrder(), expectVal)
print("Test: insert checking with post order traversal")
expectVal = [7, 25, 10, 38, 40, 30, 60, 80, 70, 50]
assert_equal(myTree.printPostOrder(), expectVal)
expectVal = [91, 81, 71, 61, 51, 41, 31, 21, 11, 1]
assert_equal(myTree2.printPostOrder(), expectVal)
print("Test: insert checking with pre order traversal")
expectVal = [50, 30, 10, 7, 25, 40, 38, 70, 60, 80]
assert_equal(myTree.printPreOrder(), expectVal)
expectVal = [1, 11, 21, 31, 41, 51, 61, 71, 81, 91]
assert_equal(myTree2.printPreOrder(), expectVal)
print("Success: test_insert_traversals")
def test_max_min_nodes (self):
myTree = BinaryTree()
myTree.insert(5)
myTree.insert(1)
myTree.insert(21)
print("Test: max node")
assert_equal(myTree.maxNode(), 21)
myTree.insert(32)
assert_equal(myTree.maxNode(), 32)
print("Test: min node")
assert_equal(myTree.minNode(), 1)
print("Test: min node inserting negative number")
myTree.insert(-10)
assert_equal(myTree.minNode(), -10)
print("Success: test_max_min_nodes")
def test_delete (self):
myTree = BinaryTree()
myTree.insert(5)
print("Test: delete")
myTree.delete(5)
assert_equal(myTree.treeIsEmpty(), True)
print("Test: more complex deletions")
[myTree.insert(x) for x in range(1, 5)]
myTree.delete(2)
assert_equal(myTree.root.rightChild.data, 3)
print("Test: delete invalid value")
assert_equal(myTree.delete(100), False)
print("Success: test_delete")
def main():
testing = TestBinaryTree()
testing.test_insert_traversals()
testing.test_max_min_nodes()
testing.test_delete()
if __name__=='__main__':
main()
In [10]:
%run -i test_binary_search_tree.py