# //Lists are linear but trees are nonlinear
# //Often working with binary trees and specifically binary search trees
# //SL is techically a special case tree
# //Root: top node of tree
# //Child: node directly connected to another node when moving away from root
# //Parent: converse notion of child
# //Siblings: group of node with same parent
# //Leaf: node with no children
# //Edge: connection betweeen one node and another (often arrows)
# //Used for HTML DOM, network routing, abstract syntax trees, folder organization, AI, best possible move (decision tree)
# //We will focus on binary search tree (can only have at most 2 child nodes)
# //For each node, everything to left is smaller. Right >> bigger
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
#adds number to correct place
def insert(self, value):
#creates new Node
new_node = Node(value)
#start at root
#if no root exists, root becomes new_node
if self.root == None:
self.root = new_node
return self
current = self.root
while True:
#to handle special case where value is same as current node
#you can return None or you can add a counter property
if value == current.value:
return None
#check to see if value is less than current
if value < current.value:
#check to see if there is node to left
#if not, add new_node to left
if current.left == None:
current.left = new_node
return self
#if there is node to left, move to that node and repeat
current = current.left
#check to see if value is greater than current
else:
#check to see if there is node to right
#if not, add new_node to right
if current.right == None:
current.right = new_node
return self
#if there is node to right, move to that node and repeat
current = current.right
#find() returns value while contains() returns boolean
#find will point to entire node
def find(self, value):
#check to see if there is root and if not, we are done!
if self.root == None:
return False
current = self.root
found = False
while current and not found:
#if value is less than current
if value < current.value:
#check to see if there is node to left
#if there is, move to that node and repeat
current = current.left
#if not, we ar edone because current will no longer exist
#if value is greater than current
elif value > current.value:
#check to see if there is node to right
#if there is, move to that node and repeat
current = current.right
#if not, we are done because current will no longer exist
else:
found = True
if not found:
return None
return current
def contains(self, value):
if self.root == None:
return False
current = self.root
found = False
while current and not found:
if value < current.value:
current = current.left
elif value > current.value:
current = current.right
else:
return True
return False
t = BinarySearchTree()
t.insert(3)
t.insert(5)
t.insert(2)
t.insert(-1)
t.insert(6)
t.find(6)
t.contains(6)
# // Insertion and Search: O(log N) VERY GOOD
# // Not guaranteed if BST is a one sided tree (choose a different root)
# // 10
# // 5 13
# // 2 7 11 16
# // tree = BinarySearchTree()
# // tree.insert(10)
# // tree.insert(5)
# // tree.insert(13)
# // tree.insert(11)
# // tree.insert(2)
# // tree.insert(16)
# // tree.insert(7)
# // tree.find(7) >> will point to node with 7
# // tree.contains(6) >> False
# //Primitive way of making Tree before insert()
# // tree = BinarySearchTree()
# // tree.root = Node(10)
# // tree.root.right = Node(15)
# // tree.root.left = Node(7)
# // tree.root.left.right = Node(9)
Comments