BST Tree Traversals (DFS and BFS) Recursively and Iteratively

BST_traversals.py

class Node: 
	def __init__ (self, v):  
		self.right=None 
		self.left=None
		self.data=v



# BFS 
def printBFS(root): #iteratively 
	q=[]
	q.append(root)
	
	while len(q) >0:
		print(q[0].data, end=" ")
		n=q.pop(0)
		if n.left:
			q.append(n.left)
		if n.right:
			q.append(n.right)
		
		
#DFS Inorder 		
def printDFS_In(root): # LpR #iteratively
    n = root  
    s = [] 
    while True: 
        if n: 
            s.append(n) 
            n = n.left  
        elif s: 
            n = s.pop() 
            print(n.data, end=" ")
            n = n.right  
        else: 
            break
			
def printDFS_In_rec(root): # LpR #recursively 
	if root:
		printDFS_In_rec(root.left)
		print(root.data, end=" ")
		printDFS_In_rec(root.right)


#DFS Postorder 	        
def printDFS_Post_rec(root): # LRp #recursively 
	if root:
		printDFS_Post_rec(root.left)
		printDFS_Post_rec(root.right)
		print(root.data, end=" ")
		
	        
def printDFS_Post(root): #LRp -> pLR #iteratively
    s1 = [] 
    s2 = [] 
    s1.append(root) 
    while s1: 
        node = s1.pop() # Pop item from s1 and
        s2.append(node) # append it to s2 
      
           
        if node.left: # Push left and right children of removed item to s1
            s1.append(node.left) 
        if node.right: 
            s1.append(node.right) 
  
        # Print all elements of second stack 
    while s2: 
        node = s2.pop() 
        print (node.data, end=" ")
		
		
		
		
		
#DFS Preorder 			
def printDFS_Pre_rec(root): # pLR #recursively 
	if root:
		print(root.data, end=" ")
		printDFS_Pre_rec(root.left)
		printDFS_Pre_rec(root.right)

        
def printDFS_Pre(root): # pLR -> pRL cuz iterative we need it to pop first  #iteratively
	n = root  
	s = [] 
	s.append(n)
	while s: 
		n = s.pop() 
		print(n.data, end=" ")
		if n.right:
			s.append(n.right) 
		if n.left:
			s.append(n.left)

  
  
  
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
#root.right.left = Node(6) 
#root.right.right = Node(7) 


print ("bfs" , end=" " )  
printBFS(root)

print() 
print ("dfs_in" , end=" " )  
printDFS_In(root)
print (" =>  dfs_in_rec" , end=" " )  
printDFS_In_rec(root)


print() 
print ("dfs_pre" , end=" " )  
printDFS_Pre(root)
print (" => dfs_pre_rec", end=" " ) 
printDFS_Pre_rec(root)

print() 
print ("dfs_post" , end=" " )  
printDFS_Post(root)
print (" => dfs_post_rec", end=" " )  
printDFS_Post_rec(root)