Inorder Traversal in Binary Trees

Tree traversal is the process of visiting every node in a tree exactly once in a systematic way. There are several types of tree traversals:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
• Level Order Traversal

In this blog, we'll focus on inorder traversal, its concept, and its implementation using both recursive and iterative approaches.

Understanding Inorder Traversal

Inorder traversal follows the order:

1. Visit the left subtree.
2. Visit the root node.
3. Visit the right subtree.

For example, consider the following binary tree:

                3
               / \
              4   5
             / \   \
            6   7   8
        

In inorder traversal, the nodes will be visited in the following order: 6, 4, 7, 3, 5, 8.

Recursive Approach

The recursive approach for inorder traversal is simple and uses the concept of recursion to visit nodes in the order Left → Root → Right.

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

# Recursive Inorder Traversal
def inorder_recursive(root):
    if root:
        inorder_recursive(root.left)  # Traverse left subtree
        print(root.value, end=" ")   # Process root
        inorder_recursive(root.right)  # Traverse right subtree

# Example Usage
if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(4)
    root.right = TreeNode(5)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(8)

    print("Inorder Traversal (Recursive):")
    inorder_recursive(root)
        

Iterative Approach

The iterative approach uses a stack to mimic the system's recursive call stack. It helps when recursion is not allowed or when stack overflow issues might occur for large trees.

# Iterative Inorder Traversal
def inorder_iterative(root):
    stack = []
    current = root

    while stack or current:
        # Reach the leftmost node of the current node
        while current:
            stack.append(current)
            current = current.left

        # Current must be None at this point
        current = stack.pop()
        print(current.value, end=" ")  # Process the root

        # Visit the right subtree
        current = current.right

# Example Usage
if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(4)
    root.right = TreeNode(5)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(8)

    print("\nInorder Traversal (Iterative):")
    inorder_iterative(root)
        

Conclusion

Both recursive and iterative approaches to inorder traversal are essential to understand as they cater to different use cases. The recursive method is simpler and intuitive, while the iterative method is better for avoiding stack overflow in large trees.

Let us know which approach you prefer in the comments! Stay tuned for our next post on postorder traversal.