Previous Topic

What Is In-Order Traversal?

In-order traversal is a way to systematically visit every node in a binary tree using the order: left subtree → node → right subtree. It is one of the three classic depth-first traversals, alongside pre-order and post-order.

For a binary search tree (BST), in-order traversal yields the node values in sorted order. This property underpins many BST operations and interview problems.

Example

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

In-order sequence: 1, 2, 3, 4, 5, 6, 7

Recursive Algorithm

function inorder(node):
    if node is null:
        return
    inorder(node.left)
    visit(node)        # e.g., print node.value or collect it in a list
    inorder(node.right)

Time complexity: O(n) visits each node once.
Space complexity: O(h) call stack, where h is the tree height (O(log n) for balanced trees, O(n) for skewed trees).

Iterative Algorithm (Using a Stack)

function inorder_iterative(root):
    stack = empty stack
    curr = root
    while curr is not null or stack is not empty:
        # Go as left as possible
        while curr is not null:
            stack.push(curr)
            curr = curr.left
        # Visit node
        curr = stack.pop()
        visit(curr)
        # Traverse right subtree
        curr = curr.right

This avoids recursion and gives the same O(n) time with O(h) explicit stack space.

Morris Traversal (O(1) Extra Space)

Morris traversal creates temporary “threads” to predecessors to traverse without a stack or recursion:

function inorder_morris(root):
    curr = root
    while curr is not null:
        if curr.left is null:
            visit(curr)
            curr = curr.right
        else:
            # Find rightmost of left subtree (predecessor)
            pred = curr.left
            while pred.right is not null and pred.right != curr:
                pred = pred.right
            if pred.right is null:
                pred.right = curr      # create thread
                curr = curr.left
            else:
                pred.right = null      # remove thread
                visit(curr)
                curr = curr.right

Morris traversal runs in O(n) time and O(1) extra space, but temporarily modifies pointers during execution.

Why It Matters

• Sorted output for BSTs: Extracts keys in non-decreasing order.
• Order-sensitive tasks: Find the k-th smallest element, merge/convert BSTs to arrays, or generate sorted lists.
• Validation: Check if a tree is a valid BST by verifying the in-order sequence is non-decreasing.
• Expression trees: Produces infix notation from binary expression trees (with parentheses as needed).

Common Pitfalls

• Forgetting the base case (null check) in recursion.
• Accidentally using pre-order or post-order ordering.
• Stack overflow on very deep/skewed trees when using recursion; prefer iterative methods or ensure balanced trees.
• Handling duplicates in BSTs: ensure a consistent policy (e.g., left subtree holds <= or < keys).

Edge Cases

• Empty tree: Visit nothing.
• Single node: Visit the node itself.
• Skewed tree: Complexity degrades to O(n) space for recursion/stack; Morris remains O(1) extra space.

Practice Ideas

• Print a BST in sorted order using recursive and iterative in-order traversal.
• Return the k-th smallest element in a BST.
• Validate a BST using in-order traversal with a running previous value.
• Implement Morris traversal and compare memory usage with the stack-based approach.

Next Topic