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)
