Morris Traversal Inorder Without Stack in DSA C

Mental Model

We visit nodes in order without using extra memory by temporarily linking nodes to their inorder predecessor.

Analogy: Imagine walking through a garden where you tie a ribbon from each tree to the previous one you visited, so you can return without getting lost or carrying a map.

    4
   / \
  2   5
 / \
1   3

Start at root (4), no extra stack, use temporary links to remember path.

Dry Run Walkthrough

Input: Binary tree: 4 -> 2 -> 1, 3 -> 5 (root 4, left child 2 with children 1 and 3, right child 5)

Goal: Print nodes in inorder: 1 -> 2 -> 3 -> 4 -> 5 without using stack or recursion

Step 1: Start at root (4), find predecessor in left subtree (3), link 3's right to 4

4 ↑
2 -> 1, 3 -> [3.right->4]
5

Why: We create a temporary link to return to 4 after left subtree is done

Step 2: Move to left child (2), find predecessor (1), link 1's right to 2

4 -> [4.left->2]
2 ↑
1 -> [1.right->2]
3 -> [3.right->4]
5

Why: Temporary link from 1 to 2 to return after visiting 1

Step 3: Move to left child (1), no left child, print 1, remove link from 1 to 2, move to 2

1 ↑ (printed)
2 -> 3 -> [3.right->4]
4 -> 5

Why: Leaf node visited, print and return to 2 by removing temporary link

Step 4: At 2, print 2, move to right child (3)

2 ↑ (printed)
3 -> [3.right->4]
4 -> 5

Why: After left subtree done, print current and move right

Step 5: At 3, no left child, print 3, remove link from 3 to 4, move to 4

3 ↑ (printed)
4 -> 5

Why: Leaf node visited, print and return to 4 by removing temporary link

Step 6: At 4, print 4, move to right child (5)

4 ↑ (printed)
5

Why: After left subtree done, print current and move right

Step 7: At 5, no left child, print 5, traversal ends

5 ↑ (printed)

Why: Leaf node visited, print and no more nodes

Result:

1 -> 2 -> 3 -> 4 -> 5 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Morris Inorder Traversal
void morrisInorder(Node* root) {
    Node* curr = root;
    while (curr != NULL) {
        if (curr->left == NULL) {
            printf("%d -> ", curr->data); // print current node
            curr = curr->right; // move right
        } else {
            // Find inorder predecessor
            Node* pred = curr->left;
            while (pred->right != NULL && pred->right != curr) {
                pred = pred->right; // move to rightmost
            }
            if (pred->right == NULL) {
                pred->right = curr; // create link
                curr = curr->left; // move left
            } else {
                pred->right = NULL; // remove link
                printf("%d -> ", curr->data); // print current
                curr = curr->right; // move right
            }
        }
    }
    printf("null\n");
}

int main() {
    // Build tree: 4
    //            /   \
    //           2     5
    //          / \
    //         1   3
    Node* root = newNode(4);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(3);

    morrisInorder(root);
    return 0;
}

while (curr != NULL) {

continue traversal until all nodes visited

if (curr->left == NULL) {

if no left child, print and move right

printf("%d -> ", curr->data);

print current node data

curr = curr->right;

move to right child

Node* pred = curr->left;

find inorder predecessor in left subtree

while (pred->right != NULL && pred->right != curr) { pred = pred->right; }

move to rightmost node of left subtree or existing link

if (pred->right == NULL) { pred->right = curr; curr = curr->left; }

create temporary link and move left

else { pred->right = NULL; printf(...); curr = curr->right; }

remove link, print current, move right

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because each edge is visited at most twice during traversal

Space: O(1) because no extra stack or recursion is used, only temporary links

vs Alternative: Compared to recursion or stack-based inorder traversal which use O(h) space, Morris traversal uses constant space by modifying tree temporarily

Edge Cases

Empty tree (root is NULL)

No output, traversal ends immediately

DSA C

while (curr != NULL) {

Tree with single node

Print the single node and end traversal

DSA C

if (curr->left == NULL) {

Tree with no left children (all right skewed)

Print nodes in order by moving right without creating links

DSA C

if (curr->left == NULL) {

When to Use This Pattern

When asked to do inorder traversal without recursion or stack, reach for Morris Traversal because it uses temporary links to achieve O(1) space.

Common Mistakes

Mistake: Not removing the temporary link after visiting the predecessor, causing infinite loops
Fix: Ensure to set predecessor's right pointer back to NULL after printing current node

Summary

Prints inorder traversal of a binary tree without using stack or recursion by temporarily modifying tree links.

Use when you want inorder traversal with O(1) extra space and can modify the tree temporarily.

The key insight is to create and remove temporary links to predecessors to remember the path back.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to traditional methods?

easy

A. It only works on binary search trees

B. It is faster than all other traversal methods

C. It uses no extra space like stack or recursion

D. It requires a special tree structure

Solution

1. Step 1: Understand traditional inorder traversal space usage

   Traditional inorder traversal uses recursion or a stack, which requires extra memory proportional to tree height.

2. Step 2: Identify Morris Traversal space usage

   Morris Traversal modifies tree links temporarily to avoid stack or recursion, using O(1) extra space.

3. Final Answer:

   It uses no extra space like stack or recursion -> Option C

4. Quick Check:

   Morris Traversal = O(1) space [OK]

Hint: Morris uses tree links, no stack or recursion needed [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Assuming it only works on BSTs
• Believing it needs special tree nodes

2. Which of the following code snippets correctly initializes the current pointer for Morris inorder traversal in C?

easy

A. struct Node* current = root;

B. struct Node current = root;

C. Node* current = NULL;

D. struct Node* current = NULL;

Solution

1. Step 1: Understand pointer initialization in C for tree traversal

   We need a pointer to the root node to start traversal, so 'struct Node* current = root;' is correct.

2. Step 2: Check other options for correctness

   struct Node current = root; declares a struct variable, not a pointer, which is incorrect. Node* current = NULL; uses 'Node*' without 'struct' keyword, invalid in C. struct Node* current = NULL; initializes current to NULL, which won't start traversal.

3. Final Answer:

   struct Node* current = root; -> Option A

4. Quick Check:

   Pointer to root = struct Node* current = root; [OK]

Hint: Use pointer to root node: struct Node* current = root; [OK]

Common Mistakes:

• Using struct variable instead of pointer
• Omitting 'struct' keyword in C
• Initializing current to NULL instead of root

3. What is the output of the Morris inorder traversal on the following binary tree?

    2
   / \
  1   3

Assuming the traversal prints node values separated by spaces.

medium

A. 1 3 2

B. 1 2 3

C. 3 2 1

D. 2 1 3

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then root, then right subtree. For this tree, left is 1, root is 2, right is 3.

2. Step 2: Apply Morris traversal logic

   Morris traversal visits nodes in inorder without stack. The output will be "1 2 3 " as it visits left child, root, then right child.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Inorder of tree = 1 2 3 [OK]

Hint: Inorder = left, root, right; output matches this order [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Forgetting spaces in output
• Misreading tree structure

4. Identify the bug in this Morris inorder traversal snippet:

while (current != NULL) {
  if (current->left == NULL) {
    printf("%d ", current->data);
    current = current->right;
  } else {
    struct Node* pre = current->left;
    while (pre->right != NULL) {
      pre = pre->right;
    }
    pre->right = current;
    current = current->left;
  }
}

medium

A. Should use recursion instead of loop

B. Missing initialization of current pointer

C. Incorrect print statement syntax

D. The inner while loop should check pre->right != current

Solution

1. Step 1: Analyze inner while loop condition

   The inner loop finds the rightmost node in left subtree. It should stop if pre->right points back to current to avoid infinite loop.

2. Step 2: Identify correct condition

   The condition must be 'pre->right != NULL && pre->right != current' to detect if thread already exists and avoid infinite loop.

3. Final Answer:

   The inner while loop should check pre->right != current -> Option D

4. Quick Check:

   Loop condition must detect thread to current [OK]

Hint: Check thread link to current in inner loop condition [OK]

Common Mistakes:

• Not checking pre->right != current causes infinite loop
• Forgetting to restore tree links after traversal
• Confusing recursion with Morris traversal

5. Given a binary tree where some nodes have only left children, how does Morris inorder traversal handle these nodes without using stack or recursion?

hard

A. It creates temporary threads from rightmost left child back to current node

B. It skips nodes without right children

C. It uses a stack internally to track nodes

D. It converts the tree into a linked list first

Solution

1. Step 1: Understand Morris traversal threading

   Morris traversal creates temporary links (threads) from the rightmost node of left subtree back to the current node to remember where to return.

2. Step 2: Apply to nodes with only left children

   For nodes with only left children, it finds the rightmost node in left subtree (which may be the left child itself) and creates a thread back to current node, enabling traversal without stack.

3. Final Answer:

   It creates temporary threads from rightmost left child back to current node -> Option A

4. Quick Check:

   Temporary threads enable traversal without stack [OK]

Hint: Threads link back to current node from left subtree's rightmost node [OK]

Common Mistakes:

• Assuming nodes without right children are skipped
• Thinking Morris uses stack internally
• Believing tree is converted to linked list