Morris Post-order Traversal

March 2026 · 15 min read

In the Morris traversal post, we covered in-order and pre-order using temporary threads. Both were pretty clean. In-order visits the node on the second encounter. Pre-order visits it on the first encounter. The thread logic stayed the same either way.

Post-order breaks that pattern. It needs to visit the node after both its subtrees are done. That's what makes it the tricky one. This entire post is dedicated to making it crystal clear.

Why Post-order Is the Hard One

Here's the simple version. Post-order says: left, right, then me. That means when Morris uses a thread to jump back up to a node, we can't just visit it, because the right subtree hasn't happened yet. And there's a whole chain of nodes (the "right boundary" of the left subtree) that need visiting in reverse order.

Let's use this tree for the entire post:

Step through what "left, right, me" means for each node:

Notice how nodes 2, 6, and 4 are visited only after everything below them is done. In Morris traversal, when we thread back to node 4 (after finishing its left subtree), the right subtree (6, 5) hasn't even started. We can't just visit 4 at that point. We need a different strategy.

The Key Idea: Reverse-Visiting Right Boundaries

When Morris in-order detects a thread (second visit), it simply visits the current node. Morris post-order does something different: it takes the right boundary of the left subtree and visits those nodes in reverse order.

What's a "right boundary"? Starting from some node, keep going .right, .right, .right until you can't anymore. That chain of nodes is the right boundary.

For example, when we're at node 4 on its second visit:

• cur->left = node 2
• Right boundary of node 2: 2 → 3 (2's right child is 3, 3 has no right child)
• Post-order needs these visited in reverse: visit 3 first, then visit 2

How do we reverse without allocating memory? We temporarily flip the right pointers backwards (like reversing a linked list), walk through them to visit, then flip them back. Three pointer variables, zero extra allocation.

This reverse-visit is the core mechanism. Every time the algorithm detects a thread (second encounter), it reverse-visits the right boundary of the current node's left subtree. Let's see the full algorithm and trace through every step on our tree.

The Algorithm (First Attempt)

Here is the recipe, starting at the root:

1. Start at the root.
2. If current node has no left child: move right.
3. If current node has left child: find the in-order predecessor (rightmost node in left subtree).
   • First visit (predecessor's right is null): create thread, move left.
   • Second visit (predecessor's right points to current): reverse-visit the right boundary of current's left subtree, then remove thread, then move right.
4. Repeat until current is null.

Visual Step-by-Step Walkthrough

Let's trace every step on our tree, starting at the root (node 4). Watch the cursor (orange ring), threads (dashed orange arrows), and visited nodes (green filled).

The Pattern (So Far)

Every step fell into one of three buckets:

• No left child: just move right. No visiting happens.
• First visit (thread created): create thread, move left. No visiting happens.
• Second visit (thread detected): reverse-visit the right boundary of cur->left, remove thread, move right. This is the only time visiting happens.

The reverse-visits that occurred:

• Step 4: Second visit at node 2. Boundary: [1]. Visited: 1
• Step 6: Second visit at node 4. Boundary: [2, 3]. Visited: 3, 2
• Step 9: Second visit at node 6. Boundary: [5]. Visited: 5

Concatenated: 1 → 3, 2 → 5 = 1, 3, 2, 5. That is only four of six nodes. The root (4) and its right child (6) were never visited. The reverse-visit mechanism works perfectly for interior subtrees, but the root-spine falls through the cracks. We will fix this after looking at the reverse-visit logic in detail.

The Reverse-Visit Trick in Detail

The visitReversePath(from, to) function is the heart of Morris post-order. Let's break it down piece by piece.

The Problem

We have a chain of nodes connected by right pointers: A → B → C → D. We need to visit them as D, C, B, A (reverse). But we have no stack, no array, no extra memory.

The Solution: Reverse the Linked List

If you've ever reversed a singly linked list, you already know the trick. Right pointers form a "linked list." We reverse those pointers, walk the list (now it's in the order we want), then reverse again to put everything back.

The Missing Piece

The walkthrough above ended with output 1, 3, 2, 5. Two nodes are missing: 4 and 6. Why?

Reverse-visits only happen when the algorithm returns to a node via a thread. Each reverse-visit processes the right boundary of that node's left subtree. The root (node 4) is the topmost node. Nobody is above it. No thread leads to a node above the root. So the chain 4 → 6 (the root's right-spine) never becomes anyone's "right boundary of left subtree."

When the algorithm returns to node 4 on its second visit, it reverse-visits 4's left subtree's boundary (2 → 3), outputting 3, then 2. Then it moves right to 6. At 6, it reverse-visits 6's left subtree's boundary (just 5). Then it moves right, hits null, and stops. Node 6 itself was never visited. Neither was node 4.

The core issue: the algorithm only visits nodes as part of right boundaries. The root and its right descendants are never part of any right boundary, because nothing sits above them.

The Fix: The Dummy Node

The fix is simple. Create a fake node called D (the "dummy") that sits above the root:

• D.left = root
• D.right = null
• The algorithm starts at D, not at the root

Now the root and its right-spine sit inside D's left subtree. The rightmost node in the entire tree (node 6) will thread back to D. When the algorithm returns to D on its second visit, it reverse-visits D's left subtree's right boundary: 4 → 6, outputting 6, then 4. The previously missing nodes are now covered, completing the post-order: 1, 3, 2, 5, 6, 4.

The dummy is a single stack variable (not heap-allocated), is never part of the output, and adds zero complexity to the logic. It just gives the algorithm a clean entry point where every node, including the root, lives inside someone's left subtree.

The Complete Code

void morrisPostorder(TreeNode* root) {
    TreeNode dummy;
    dummy.left = root;
    dummy.right = nullptr;
    TreeNode* cur = &dummy;

    while (cur) {
        if (!cur->left) {
            // Case 1: No left child. Just move right.
            cur = cur->right;
        } else {
            // Find the in-order predecessor
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur)
                pred = pred->right;

            if (!pred->right) {
                // Case 2a: First visit. Create thread, go left.
                pred->right = cur;
                cur = cur->left;
            } else {
                // Case 2b: Second visit!
                // Reverse-visit the right boundary of cur->left
                visitReversePath(cur->left, pred);
                // Remove the thread
                pred->right = nullptr;
                // Move right
                cur = cur->right;
            }
        }
    }
}

// Visit nodes from 'from' to 'to' in REVERSE order
void visitReversePath(TreeNode* from, TreeNode* to) {
    // Step 1: Reverse the right pointers
    reversePath(from, to);

    // Step 2: Walk from 'to' following the (now reversed) right
    // pointers. This visits them deepest-first.
    for (TreeNode* p = to; ; p = p->right) {
        visit(p);
        if (p == from) break;
    }

    // Step 3: Reverse back to restore original structure
    reversePath(to, from);
}

// Reverse right pointers along: from -> ... -> to
// (standard singly-linked-list reversal)
void reversePath(TreeNode* from, TreeNode* to) {
    if (from == to) return;
    TreeNode* prev = from;
    TreeNode* cur = from->right;
    while (prev != to) {
        TreeNode* next = cur->right;
        cur->right = prev;     // flip this pointer
        prev = cur;
        cur = next;
    }
}

Complexity

• Time: O(n). The main loop is identical to Morris in-order, which is O(n). The reverse-visit adds work, but each edge in the tree participates in at most one reversal. Total reversal work across all reverse-visits: O(n).
• Space: O(1). The dummy node lives on the stack (single variable, not heap). The reversal uses three pointers (prev, cur, next). No arrays, no stack, no recursion, no allocation.

Interactive Animation (Complete, with Dummy Node)

Summary

• Morris post-order uses the same thread logic as Morris in-order.
• The two additions: a dummy node as the starting point, and a reverse-visit of the right boundary on second encounter (instead of just visiting the current node).
• The reverse-visit works by temporarily flipping right pointers (like reversing a linked list), visiting the nodes, then restoring the pointers. O(1) extra space.
• The dummy node ensures the root and its right-spine get visited at the very end.
• Total: O(n) time, O(1) space. The tree is fully restored afterwards.