4 Types Of Binary Tree Traversal | Algorithm Implementation | Iterative Way | Code Snippet

The tree is one of the most important data structures in computer science. We are going to see the Python implementation of tree traversals. In this blog, we will see only iterative implementation.

Pre Order Traversal

class TreeNode:
	
	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

def preorder_traversal(root):
	if root is None:
		return

	node_stack = [root]

	while node_stack:

		node = node_stack.pop()
		print(node.val)

		if node.right:
			node_stack.append(node.right)
		if node.left:
			node_stack.append(node.left)

In Order Traversal

class TreeNode:
	
	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

def inorder_traversal(root):

	node_stack = []
	
	while root or node_stack :
		while root:
			node_stack .append(root)
			root = root.left
		
		root = node_stack.pop()
		print(root.val)
		root = root.right

Post Order Traversal

class TreeNode:
	
	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

def postorder_traversal(root):
    result = []
    node_stack = [root]

    while node_stack:
        node = node_stack.pop()
        if node:
            result.append(node.val)
            node_stack.append(node.left)
            node_stack.append(node.right)

    print('\n'.join(result[::-1]))

Level Order Traversal

class TreeNode:
	
	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

def level_order(root):

	if root is None:
		return

	queue = [root]
	
	while queue:
		node = queue.pop()
		print(node.val)
		
		if node.left:
			queue.insert(0, node.left)
		if node.right:
			queue.insert(0, node.right)