Home/Questions/Q 3522
Next
In Process

RTSALL Latest Articles

aarav0
Asked: 2026-09-11T09:51:56-05:00 In: ,

How to traverse a Binary Tree in O(1) memory without recursion or stack (Morris Traversal)?

In our embedded C++ runtime, each thread has a strictly limited stack frame (64KB). When traversing deeply skewed binary trees with millions of nodes, recursive DFS triggers a stack overflow, and allocating an explicit heap stack (std::vector) exceeds our device RAM limit.

I heard about Morris Traversal which claims to do a full Inorder/Preorder tree traversal in strict O(1) auxiliary space without a call stack. How does it work under the hood, and does it corrupt the tree structure?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhishek
    Begginer

    Here is the full modern C++ implementation of Morris Inorder Traversal. Notice how it cleanly establishes and tears down temporary predecessor right-pointers, completely restoring the original tree topology before returning.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> morrisInorder(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;

    while (curr != nullptr) {
        if (curr->left == nullptr) {
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            TreeNode* pred = curr->left;
            while (pred->right != nullptr && pred->right != curr) {
                pred = pred->right;
            }

            if (pred->right == nullptr) {
                pred->right = curr; // Create thread
                curr = curr->left;
            } else {
                pred->right = nullptr; // Break thread (tree restored!)
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    auto inorder = morrisInorder(root);
    std::cout << "Morris Inorder: ";
    for (int x : inorder) std::cout << x << " ";
    std::cout << "n";

    return 0;
}

    Complexity: O(N) time and strict O(1) auxiliary space. No call stack or heap allocation.

    • 0
  2. Abhay Tiwari
    Begginer

    Morris Traversal is one of the most brilliant algorithms in computer science. It solves the exact constraint you’re facing: how do you traverse a tree without spending any extra memory on a stack?

    1. The Core Secret: Threaded Binary Trees

    When you are at a node and go deep into its left subtree, how do you get back up to the node without a parent pointer or call stack? Normally, you need a stack to remember the return path.

    J. H. Morris realized something clever: in every binary tree, about half of all pointers are NULL! Every leaf node has a null right child that is sitting there doing nothing.

    Morris repurposes these unused null pointers as temporary bridge wires (called “threads”) back to the inorder successor:

    1. Find the node’s inorder predecessor (the rightmost node in the left subtree).
    2. If its right pointer is null, point it back to the current node: predecessor->right = current. Then move current = current->left.
    3. If its right pointer is already pointing to current, that means you have already finished visiting the left subtree! You print/record current->val, restore the pointer to null (repairing the tree), and move current = current->right!

    When the algorithm finishes, the tree is 100% restored to its original state. Zero memory allocated, zero permanent mutations!

    Clean C++20 Morris Inorder Traversal

    #include <vector>
#include <cstdint>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> morrisInorderTraversal(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;

    while (curr != nullptr) {
        if (curr->left == nullptr) {
            // Case 1: No left child, visit this node and move right
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            // Case 2: Find inorder predecessor (rightmost in left subtree)
            TreeNode* pred = curr->left;
            while (pred->right != nullptr && pred->right != curr) {
                pred = pred->right;
            }

            if (pred->right == nullptr) {
                // First time visiting: create temporary thread
                pred->right = curr;
                curr = curr->left;
            } else {
                // Second time visiting: restore tree and visit curr
                pred->right = nullptr;
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

    Complexity & Trade-offs

    • Time Complexity: O(N). Even though we search for predecessors, each edge in the tree is traversed at most 3 times (once to find predecessor, once to create thread, once to remove thread). 3 * (N - 1) = O(N).
    • Space Complexity: O(1) auxiliary space. Just two pointers (curr and pred). No call stack, no heap allocations.
    • Thread-Safety Warning: Because Morris Traversal temporarily mutates right pointers during execution, it is not safe for concurrent readers on the same tree instance. If multiple threads read the tree simultaneously, use standard recursive DFS with a large stack or an explicit thread-local queue.
    • 0