@@ -46,15 +46,13 @@ def build_tree():
4646 node_found .right = right_node
4747 q .put (right_node )
4848
49-
5049def pre_order (node ):
5150 if not isinstance (node , TreeNode ) or not node :
5251 return
5352 print (node .data , end = " " )
5453 pre_order (node .left )
5554 pre_order (node .right )
5655
57-
5856def in_order (node ):
5957 if not isinstance (node , TreeNode ) or not node :
6058 return
@@ -84,6 +82,50 @@ def level_order(node):
8482 if node_dequeued .right :
8583 q .put (node_dequeued .right )
8684
85+ #iteration version
86+ def pre_order_iter (node ):
87+ if not isinstance (node , TreeNode ) or not node :
88+ return
89+ stack = []
90+ n = node
91+ while n or stack :
92+ while n : #start from root node, find its left child
93+ print (n .data , end = " " )
94+ stack .append (n )
95+ n = n .left
96+ #end of while means current node doesn't have left child
97+ n = stack .pop ()
98+ #start to traverse its right child
99+ n = n .right
100+
101+ def in_order_iter (node ):
102+ if not isinstance (node , TreeNode ) or not node :
103+ return
104+ stack = []
105+ n = node
106+ while n or stack :
107+ while n :
108+ stack .append (n )
109+ n = n .left
110+ n = stack .pop ()
111+ print (n .data , end = " " )
112+ n = n .right
113+
114+ def post_order_iter (node ):
115+ if not isinstance (node , TreeNode ) or not node :
116+ return
117+ stack1 , stack2 = [], []
118+ n = node
119+ stack1 .append (n )
120+ while stack1 : #to find the reversed order of post order, store it in stack2
121+ n = stack1 .pop ()
122+ if n .left :
123+ stack1 .append (n .left )
124+ if n .right :
125+ stack1 .append (n .right )
126+ stack2 .append (n )
127+ while stack2 : #pop up from stack2 will be the post order
128+ print (stack2 .pop ().data , end = " " )
87129
88130if __name__ == '__main__' :
89131 print ("\n ********* Binary Tree Traversals ************\n " )
@@ -104,3 +146,15 @@ def level_order(node):
104146 print ("\n ********* Level Order Traversal ************" )
105147 level_order (node )
106148 print ("\n ******************************************\n " )
149+
150+ print ("\n ********* Pre Order Traversal - Iteration Version ************" )
151+ pre_order_iter (node )
152+ print ("\n ******************************************\n " )
153+
154+ print ("\n ********* In Order Traversal - Iteration Version ************" )
155+ in_order_iter (node )
156+ print ("\n ******************************************\n " )
157+
158+ print ("\n ********* Post Order Traversal - Iteration Version ************" )
159+ post_order_iter (node )
160+ print ("\n ******************************************\n " )
0 commit comments