Code Snippets · September 19, 2020

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)