# //Tree Traversal (visit every node once) 
# //Heavy on recursion 
 
# //Breadth-first (BFS) vs. Depth-first (DFS) 
 
# // DFS: 
# // 1) in order (go in order of value)
# // 2) pre order (start at root)
# // 3) post order (start at botom)
 
 
# //When to use BFS vs. DFS: 
# //For a fully loaded (wide) tree, BFS queue will be overloaded in the start (overloaded space complexity)
# //For a longer tree, DFS will take more memory (more rare, Trees are usually wide)
# //Big O for both is same 
 
# //In order: useful if you want sorted array at end (you don't really know what the root is bc it's in the middle)
# //PreOrder: useful to "export a tree" so that it can be copied bc it flattens it 

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 
        
  #Breadth first search iterative using queue 
  def BFS(self):
    node = self.root 
    #we will return data 
    data = [] 
    queue = [] 
    #place root node inside queue (recall FIFO)
    queue.append(node) 
    #while queue is not empty 
    while len(queue) > 0: 
      #dequeue node from queue and append to data  
      node = queue.pop(0)
      data.append(node) 
      #if there is left on node dequeued, add to queue 
      if node.left: 
        queue.append(node.left) 
      #if there is right on node dequeued, add to queue 
      if node.right: 
        queue.append(node.right) 
      #above two lines of code could be changed if it was a ternary tree, etc. instead of binary 
      #just loop for all children 
    return data 
  
  #parent down uses recursive 
  def DFSPreoder(self): 
    data = [] 
    #if you want to DFS not from root, create a variable here named current and specify which node to start from 
    #helper function 
    def traverse(node): 
      #all of root node's left will happen first, then right 
      #for other types of DFS, just tweak this order 
      data.append(node.value) 
      if node.left:
        traverse(node.left)
      if node.right: 
        traverse(node.right)
    
    traverse(self.root) 
    return data 
  
  #children up, root should be last value 
  def DFSPostOrder(self): 
    data = []
    
    def traverse(node): 
      if node.left:
        traverse(node.left)
      if node.right: 
        traverse(node.right)
      data.append(node.value)
    
    traverse(self.root)
    return data 
  
  #result data list should be sorted 
  def DFSInOrder(self):
    data = []
    def traverse(node): 
      if node.left: 
        traverse(node.left)
      data.push(node.value)
      if node.right: 
        traverse(node.right)
    traverse(self.root)
    return data 

t = BinarySearchTree() 
t.insert(1)
t.insert(5)
t.insert(6)
t.insert(2)
t.insert(0) 
t.insert(-1)
t.insert(7) 

print(t.DFSInOrder())