Morris Traversal Inorder Without Stack in DSA C++ - Build from Scratch

Morris Traversal Inorder Without Stack

📖 Scenario: You are working with a binary tree data structure. Normally, to visit all nodes in order (left, root, right), you use extra memory like a stack or recursion. But here, you will learn a clever way to do this without extra memory, called Morris Traversal.This method temporarily changes the tree links to remember where to go next, then restores the tree back to normal.

🎯 Goal: Build a program that performs an inorder traversal of a binary tree using Morris Traversal technique without using stack or recursion. The program will print the values of nodes in inorder sequence.

📋 What You'll Learn

Create a binary tree node structure with integer data and left and right pointers

Build a sample binary tree with exact nodes and structure

Implement Morris Traversal inorder function without using stack or recursion

Print the inorder traversal output as space-separated node values

💡 Why This Matters

🌍 Real World

Morris Traversal is useful in systems with limited memory where recursion or stack usage is costly, such as embedded systems or large trees.

💼 Career

Understanding Morris Traversal shows mastery of tree traversal algorithms and memory optimization, valuable for software engineers working on performance-critical applications.

1

Create the Binary Tree Node Structure and Sample Tree

Define a struct called Node with an int data, and two pointers Node* left and Node* right. Then create a binary tree with root node root having value 1, left child 2, right child 3, left child's left child 4, and left child's right child 5.

DSA C++

// Define struct Node and create the binary tree with root and children
// Your code here

Hint

Start by defining the node structure with constructor. Then create nodes and link them exactly as described.

2

Create a Pointer Variable for Traversal

Create a pointer variable called current and set it to point to the root node.

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);

// Create pointer current and set it to root
// Your code here

Hint

Just create a pointer named current and assign it the root node.

3

Implement Morris Inorder Traversal Logic

Write a while loop that runs while current is not nullptr. Inside the loop, if current->left is nullptr, print current->data followed by a space, then move current to current->right. Otherwise, find the rightmost node in current->left subtree (called predecessor). If predecessor->right is nullptr, set it to current and move current to current->left. Else, set predecessor->right to nullptr, print current->data followed by a space, and move current to current->right.

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);

Node* current = root;

// Implement Morris inorder traversal loop here
// Your code here

Hint

Use the Morris Traversal steps carefully: find predecessor, create temporary link, print data when left is null or after restoring links.

4

Print the Final Inorder Traversal Output

Add a std::cout statement to print a newline character after the Morris traversal loop to end the output cleanly.

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);

Node* current = root;

while (current != nullptr) {
    if (current->left == nullptr) {
        std::cout data right;
    } else {
        Node* predecessor = current->left;
        while (predecessor->right != nullptr && predecessor->right != current) {
            predecessor = predecessor->right;
        }
        if (predecessor->right == nullptr) {
            predecessor->right = current;
            current = current->left;
        } else {
            predecessor->right = nullptr;
            std::cout data right;
        }
    }
}

// Print newline after traversal
// Your code here

Hint

After printing all nodes with spaces, print a newline to end output cleanly.