Created
December 9, 2019 12:32
-
-
Save ezzeldinadel/492362414c8b6d7c22681696737b6521 to your computer and use it in GitHub Desktop.
BST Tree Traversals (DFS and BFS) Recursively and Iteratively
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment