tldr:

pre-order: visit, left, right

in-order: left, visit, right

post-order: left, right, visit

A traversal iterates through a collection, one item at a time, in order to access or visit each item. The actual operation performed when “visiting” an item is application dependent, but it could involve something as simple as printing the data item or saving it to a file.

With a linear structure such as a linked list, the traversal is rather easy since we can start with the first node and iterate through the nodes, one at at time, by following the links between the nodes. But how do we visit every node in a binary tree?

There is no single path from the root to every other node in the tree. Remember, the links between the nodes lead us down into the tree. If we were to simply follow the links, once we reach a leaf node we cannot directly access any other node in the tree.

inorder: 1, 4, 12, 23, 29, 37, 41, 60, 71, 84, 90, 100

preorder: 60, 12, 4, 1, 41, 29, 23, 37, 90, 71, 84, 100

postorder: 1, 4, 23, 37, 29, 41, 12, 84, 71, 100, 90, 60

	# traverse the left subtree
	# visit the node
	# traverse the right subtree
	def inorder(self, subtree):
		if subtree != None:
			self.inorder(subtree.left)
			print(subtree.data, subtree.key)
			self.inorder(subtree.right)

	# visit the node
	# traverse the left subtree
	# traverse the right subtree
	def preorder(self, subtree):
		if subtree != None:
			print(subtree.data, subtree.key)
			self.inorder(subtree.left)
			self.inorder(subtree.right)

	# visit the node
	# traverse the left subtree
	# traverse the right subtree    
	def postorder(self, subtree):
		if subtree != None:
			self.postorder(subtree.left)
			self.postorder(subtree.right)
			print(subtree.data, subtree.key)