Tree Traversal

Morris Traversal

What is Morris Traversal?

Every traversal seen so far — pre-order, in-order, post-order, level-order — needs extra memory to remember "where to come back to": recursive traversals use the call stack, and level-order uses an explicit queue. Morris traversal is a clever technique that produces the exact same in-order sequence using O(1) extra space, no stack and no queue at all.

How Does It Work?

The trick is to temporarily repurpose the tree's own empty pointers to remember the way back. For any node with a left child, Morris traversal finds that node's in-order predecessor — the rightmost node in its left subtree — and threads a temporary link from the predecessor's (normally null) right pointer back to the current node. This thread is exactly the "return address" a stack frame or queue entry would otherwise store.

831610
Predecessor & current nodeTemporary thread

Once a node with a thread pointing at it is reached again, the algorithm recognizes the thread (its predecessor's right pointer already points at the current node), visits the node, and then removes the thread — restoring the original tree structure exactly as it was before traversal started. By the time the traversal finishes, no threads remain and the tree is completely unmodified.

Algorithm Steps

  1. Set curr to the root
  2. While curr is not null, repeat:
    • If curr has no left child: visit curr, then move curr to curr.right
    • Otherwise, find curr's in-order predecessor — the rightmost node in curr's left subtree
    • If the predecessor's right pointer is null: thread it to curr (predecessor.right = curr), then move curr to curr.left
    • If the predecessor's right pointer already points to curr: remove the thread (predecessor.right = null), visit curr, then move curr to curr.right

Time Complexity

  • Time Complexity: Each edge is traversed at most twice (once to create the thread, once to remove it) → O(n).
  • Space Complexity: No recursion stack, no queue — only a couple of pointer variables → O(1).

Time Complexity Analysis

Advertisement

Morris traversal needs O(1) extra space — no recursion, no explicit stack or queue — which is exactly why it's used in memory-constrained environments or when a tree needs to stay usable by other code while being traversed without paying any extra memory cost.

Daily DSA Challenge by Scale Engineer

Watch Morris traversal thread temporary links instead of using a stack

Tree is empty
No tree yet — insert a value or generate a random tree
Not yet visitedVisitedCurrent pointerPredecessorTemporary thread

Test Your Knowledge before moving forward!

Morris Traversal Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Morris Traversal Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Morris in-order traversal: O(n) time, O(1) space — no stack, no queue
function morrisInOrder(root) {
  const result = [];
  let curr = root;

  while (curr !== null) {
    if (curr.left === null) {
      // No left subtree — visit curr, then move right
      result.push(curr.value);
      curr = curr.right;
    } else {
      // Find the in-order predecessor: rightmost node in curr's left subtree
      let pred = curr.left;
      while (pred.right !== null && pred.right !== curr) {
        pred = pred.right;
      }

      if (pred.right === null) {
        // Create the thread and descend left
        pred.right = curr;
        curr = curr.left;
      } else {
        // Thread already exists — we've come back via it.
        // Remove it, visit curr, then move right.
        pred.right = null;
        result.push(curr.value);
        curr = curr.right;
      }
    }
  }

  return result;
}

// Usage example — tree is left completely unmodified afterward
let root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);

console.log(morrisInOrder(root)); // [1, 3, 6, 8, 10]

Done With the Learning

Mark Morris Traversal as done and view it on your dashboard

Explore Other Tree Topics

In-order Traversal

Pre-order Traversal

Post-order Traversal

Level-order Traversal

BST Insertion