In-Order Traversal

In-Order Traversal

In the previous tutorial, we explored Pre-Order Traversal.

Now, we will look at the second major Depth-First Search technique: In-Order Traversal.

This is perhaps the most famous of all tree traversals because of its special mathematical properties when dealing with sorted data.

1. What is In-Order Traversal?

Tree traversal means visiting every single node in the tree exactly one time.

Because trees are hierarchical, we need a specific, repeatable path to follow.

In-Order Traversal follows this strict path:

1. Left: First, recursively visit the entire Left subtree.
2. Root: Second, visit the current node (the Root of the subtree).
3. Right: Third, recursively visit the entire Right subtree.

The prefix "In" helps you remember that the Root is visited in the middle of the left and right children!

In-Order Traversal: Notice how the numbering moves from the bottom-left, up to the root, and down to the right.

2. A Step-by-Step Example

Let's look at the tree in the diagram above and trace the exact execution path.

Assume we have a Binary Search Tree with a Root of 10, a Left Child of 5, and a Right Child of 15. The 5 has its own children: 2 (Left) and 7 (Right). The 15 has its own children: 12 (Left) and 20 (Right).

Step 1: The Descent

• Start at the absolute Root: 10.
• Rule 1 says: Go Left. We move to 5.
• Rule 1 says: Go Left. We move to 2.
• Rule 1 says: Go Left. Node 2 has no left child!

Step 2: Processing the Leftmost Node

• We are at 2. Left is done.
• Rule 2 says: Visit the Root. We print 2.
• Rule 3 says: Go Right. No right child!
• Node 2 is fully processed. We move back up to 5.

Step 3: Moving Up

• We are back at 5. Its Left child is fully processed.
• Rule 2 says: Visit the Root. We print 5.
• Rule 3 says: Go Right. We move to 7.

Step 4: Processing the Inner Leaves

• We are at 7. Go Left? None.
• Rule 2 says: Visit the Root. We print 7.
• Go Right? None.
• Node 7 is done. We move back up to 5 (done), then back up to 10.

Step 5: The Main Root

• We are back at 10. Its entire Left subtree is fully processed.
• Rule 2 says: Visit the Root. We print 10.
• Rule 3 says: Go Right. We move to 15.

Step 6: The Right Subtree

• We are at 15. Go Left. We move to 12.
• At 12, no Left child. Visit Root: print 12. No Right child. Move up to 15.
• At 15, Left is done. Visit Root: print 15.
• Go Right. We move to 20.
• At 20, no Left. Visit Root: print 20. No Right. Move up.

Final Output: 2, 5, 7, 10, 12, 15, 20

(Notice how the final output is in perfectly sorted, ascending order!)

3. Why Use In-Order Traversal?

Every traversal has a specific superpower. What is In-Order good for?

1. Sorting Data (Binary Search Trees) If you use In-Order Traversal on a Binary Search Tree (BST), it will magically print out all the values in perfectly sorted, ascending order. This is its absolute most common use case in software engineering!

2. Flattening Trees If you want to convert a Binary Search Tree into a sorted 1D Array or Linked List, you just run an In-Order traversal and push the printed values into your array.

3. Infix Notation In mathematical expression trees, In-Order traversal generates standard human-readable math equations (like A + B).

4. Code Example (Python)

Let's write the code for In-Order Traversal.

Just like Pre-Order, the code relies heavily on Recursion. The only difference is where we place the print() statement!

# 1. Create the Node Class
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

# 2. Define the In-Order function
def inorder_traversal(node):
    # Base case: If the node is None, stop!
    if node is not None:
        # 1. Traverse the Left Subtree
        inorder_traversal(node.left)
        # 2. Visit the Root (Print it)
        print(node.data, end=" ")
        # 3. Traverse the Right Subtree
        inorder_traversal(node.right)
# 3. Build the Binary Search Tree
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.left = Node(12)
root.right.right = Node(20)
# 4. Run the Algorithm
print("In-Order Output:")
inorder_traversal(root)

5. Time and Space Complexity

• Time Complexity: O(n). Every single node in the tree is visited exactly once. Therefore, the time it takes scales linearly with the total number of nodes (n) in the tree.
• Space Complexity: O(h). Where h is the maximum height of the tree. This space is required by the computer's Call Stack to remember where it was during the recursive calls.
  • In a perfectly balanced tree, the height is log n, making the space complexity O(log n).
  • In a worst-case scenario (a heavily unbalanced tree that looks like a straight line), the height is n, making it O(n) space.