Morris Traversal Explained: O(1) Space Inorder, Preorder & Edge Cases

Every serious DSA practitioner hits a wall when they realise that recursive tree traversal — elegant as it is — carries a hidden O(h) space cost on the call stack, where h is the tree height. On a skewed tree with a million nodes, that's a million stack frames. In memory-constrained environments — embedded systems, high-throughput stream processors, certain competitive programming judges — that cost is unacceptable. Morris Traversal, published by Joseph Morris in 1979, solves this with an audacious idea: temporarily rewrite the tree's own null pointers to encode traversal state, then undo every change before you leave.

The problem Morris Traversal solves is surprisingly fundamental: how do you know where to 'go back' after finishing a left subtree, without a stack keeping that address for you? The classic iterative approach just swaps the implicit call stack for an explicit one — same asymptotic cost, different constant. Morris's insight was that null right-child pointers in inorder predecessors are wasted space. There are exactly n-1 edges in a binary tree, leaving n+1 null pointers sitting idle. He used a subset of those to store temporary back-links — called 'threads' — that guide traversal back up the tree without any auxiliary structure.

By the end of this article you'll be able to implement Morris Inorder and Morris Preorder from scratch, explain the thread-creation and thread-detection logic in an interview, reason about exactly when the tree is in a temporarily modified state (and why that matters for concurrent code), and confidently handle every edge case — single nodes, skewed trees, complete binary trees, and trees with duplicate values.

What is Morris Traversal of Binary Tree?

Morris Traversal of Binary Tree is a core concept in DSA. Rather than starting with a dry definition, let's see it in action and understand why it exists.

// TheCodeForge — Morris Traversal of Binary Tree example
// Always use meaningful names, not x or n
public class ForgeExample {
    public static void main(String[] args) {
        String topic = "Morris Traversal of Binary Tree";
        System.out.println("Learning: " + topic + " 🔥");
    }
}

Frequently Asked Questions