Morris Traversal Inorder Without Stack in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a simple tree

What is the output of the following Morris inorder traversal code on the given binary tree?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
};

// Tree structure:
//       2
//      / \
//     1   3

void morrisInorder(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* pre = current->left;
            while (pre->right != nullptr && pre->right != current) {
                pre = pre->right;
            }
            if (pre->right == nullptr) {
                pre->right = current;
                current = current->left;
            } else {
                pre->right = nullptr;
                std::cout << current->data << " ";
                current = current->right;
            }
        }
    }
}

// Call morrisInorder(root) where root is the node with data=2

A 3 2 1

B 2 1 3

C 1 2 3

D 1 3 2

💡 Hint

Remember inorder traversal visits left subtree, then node, then right subtree.

Morris inorder traversal visits nodes in ascending order for a BST. For the tree 2 with left child 1 and right child 3, the inorder is 1 2 3.

❓ Predict Output

intermediate

Output of Morris Traversal on a tree with left skew

What is the output of the Morris inorder traversal on this left skewed tree?

DSA C++

// Tree structure:
//     3
//    /
//   2
//  /
// 1

// Using the same morrisInorder function as before, called with root = node with data=3

A 3 2 1

B 1 3 2

C 2 1 3

D 1 2 3

💡 Hint

Inorder traversal visits left subtree first, so the smallest value comes first.

The inorder traversal of a left skewed tree visits nodes from bottom to top: 1 2 3.

🔧 Debug

advanced

Identify the error in this Morris traversal code snippet

What error will this Morris traversal code produce when run on a binary tree?

DSA C++

void morrisInorder(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* pre = current->left;
            while (pre->right != nullptr) {
                pre = pre->right;
            }
            if (pre->right == nullptr) {
                pre->right = current;
                current = current->left;
            } else {
                pre->right = nullptr;
                std::cout << current->data << " ";
                current = current->right;
            }
        }
    }
}

A Infinite loop

B Segmentation fault

C Compilation error

D Correct output

💡 Hint

Check the inner while loop condition for finding predecessor.

The inner while loop misses the condition to stop when pre->right == current, causing an infinite loop.

🧠 Conceptual

advanced

Why does Morris Traversal not use stack or recursion?

Which of the following best explains why Morris traversal can perform inorder traversal without using stack or recursion?

A It temporarily modifies the tree by creating threads to predecessors to remember the path back.

B It uses a hidden stack inside the CPU registers to store nodes.

C It uses a queue to store nodes instead of a stack.

D It performs traversal by visiting nodes in random order and sorting them later.

💡 Hint

Think about how the algorithm remembers where to return after visiting left subtree.

Morris traversal creates temporary links (threads) to predecessors to avoid using extra memory for stack or recursion.

🚀 Application

expert

Number of nodes visited twice in Morris Traversal on a left-skewed tree

In Morris inorder traversal of a left-skewed binary tree with N nodes, how many nodes are visited exactly twice during the traversal?

A N

B N - 1

C N + 1

D 0

💡 Hint

Consider how many temporary threads are created and removed during traversal.

Each node with a left child is visited twice: once to create a thread and once to remove it. In a left-skewed tree with N nodes, there are N-1 such nodes.