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. You want to print the values of the tree nodes in inorder sequence (left, root, right) without using extra memory like a stack or recursion.This technique is called Morris Traversal. It temporarily changes the tree structure to remember where to go next, then restores it back.

🎯 Goal: Build a C program that performs Morris inorder traversal on a given binary tree and prints the node values in inorder sequence without using stack or recursion.

📋 What You'll Learn

Define a binary tree node structure called Node with int data, Node *left, and Node *right.

Create a binary tree with exactly these nodes and connections:
Root node with data 1, left child 2, right child 3, left child of 2 is 4, right child of 2 is 5.

Implement Morris inorder traversal function called morrisInorder that prints node data in inorder without using stack or recursion.

Print the inorder traversal result on a single line separated by spaces.

💡 Why This Matters

🌍 Real World

Morris traversal is useful in systems with limited memory where recursion or stack usage is expensive, such as embedded systems or low-memory devices.

💼 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 nodes and build the tree

Define a struct called Node with int data, Node *left, and Node *right. Then create nodes with data 1, 2, 3, 4, and 5. Connect them to form the tree where node 1 is root, 2 is left child of 1, 3 is right child of 1, 4 is left child of 2, and 5 is right child of 2.

DSA C

# Define struct Node and create nodes with data 1, 2, 3, 4, 5
# Connect nodes to form the tree as described

Hint

Start by defining the Node structure. Then create each node using malloc and assign the data values. Connect the nodes by setting the left and right pointers as described.

2

Declare the Morris inorder traversal function prototype

Declare a function prototype called void morrisInorder(Node *root) above main. This function will perform the Morris inorder traversal on the tree starting from root.

DSA C

#include 
#include 

// Declare morrisInorder function prototype here

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

int main() {
    Node *root = (Node *)malloc(sizeof(Node));
    Node *node2 = (Node *)malloc(sizeof(Node));
    Node *node3 = (Node *)malloc(sizeof(Node));
    Node *node4 = (Node *)malloc(sizeof(Node));
    Node *node5 = (Node *)malloc(sizeof(Node));

    root->data = 1;
    root->left = node2;
    root->right = node3;

    node2->data = 2;
    node2->left = node4;
    node2->right = node5;

    node3->data = 3;
    node3->left = NULL;
    node3->right = NULL;

    node4->data = 4;
    node4->left = NULL;
    node4->right = NULL;

    node5->data = 5;
    node5->left = NULL;
    node5->right = NULL;

    return 0;
}

// Your code here

Hint

Write the function prototype void morrisInorder(Node *root); before the typedef struct Node declaration.

3

Implement the Morris inorder traversal function

Implement the function void morrisInorder(Node *root) that performs Morris inorder traversal. Use a pointer current starting at root. While current is not NULL, if current->left is NULL, print current->data and move current to current->right. Otherwise, find the inorder predecessor of current in the left subtree. If predecessor's right is NULL, set it to current and move current to current->left. If predecessor's right is current, set it back to NULL, print current->data, and move current to current->right. This way, you traverse the tree without stack or recursion.

DSA C

#include 
#include 

void morrisInorder(Node *root) {
    // Your code here
}

// rest of the code remains same

Hint

Use a while loop to traverse the tree with a pointer current. If current->left is NULL, print the data and move right. Otherwise, find the inorder predecessor and create or remove the temporary link accordingly.

4

Call the Morris inorder traversal and print the result

In main, after building the tree, call morrisInorder(root) to print the inorder traversal of the tree. Then print a newline character \n.

DSA C

#include 
#include 

void morrisInorder(Node *root) {
    Node *current = root;
    while (current != NULL) {
        if (current->left == NULL) {
            printf("%d ", current->data);
            current = current->right;
        } else {
            Node *predecessor = current->left;
            while (predecessor->right != NULL && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == NULL) {
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = NULL;
                printf("%d ", current->data);
                current = current->right;
            }
        }
    }
}

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

int main() {
    Node *root = (Node *)malloc(sizeof(Node));
    Node *node2 = (Node *)malloc(sizeof(Node));
    Node *node3 = (Node *)malloc(sizeof(Node));
    Node *node4 = (Node *)malloc(sizeof(Node));
    Node *node5 = (Node *)malloc(sizeof(Node));

    root->data = 1;
    root->left = node2;
    root->right = node3;

    node2->data = 2;
    node2->left = node4;
    node2->right = node5;

    node3->data = 3;
    node3->left = NULL;
    node3->right = NULL;

    node4->data = 4;
    node4->left = NULL;
    node4->right = NULL;

    node5->data = 5;
    node5->left = NULL;
    node5->right = NULL;

    // Your code here
}

Hint

Call morrisInorder(root); in main to print the inorder traversal. Then print a newline with printf("\n");.

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