Preview:
# //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)






downloadDownload PNG downloadDownload JPEG downloadDownload SVG

Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!

Click to optimize width for Twitter