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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Simple Tree

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

Tree structure:
2
/ \
1 3

Assume the traversal prints node values separated by spaces.

DSA Typescript

class Node {
  val: number;
  left: Node | null;
  right: Node | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function morrisInorder(root: Node | null): void {
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      process.stdout.write(current.val + ' ');
      current = current.right;
    } else {
      let pre = current.left;
      while (pre.right !== null && pre.right !== current) {
        pre = pre.right;
      }
      if (pre.right === null) {
        pre.right = current;
        current = current.left;
      } else {
        pre.right = null;
        process.stdout.write(current.val + ' ');
        current = current.right;
      }
    }
  }
}

const root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);
morrisInorder(root);

A 1 2 3

B 2 1 3

C 3 2 1

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 BST. For the tree with root 2, left child 1, right child 3, the inorder sequence is 1 2 3.

🧠 Conceptual

intermediate

Understanding Thread Creation in Morris Traversal

In Morris inorder traversal, what is the purpose of creating a temporary thread (link) from the inorder predecessor to the current node?

A To permanently modify the tree structure for faster future traversals

B To avoid using recursion or stack by temporarily linking back to the current node after visiting left subtree

C To store node values in a separate array for output

D To mark nodes as visited to prevent revisiting

💡 Hint

Think about how Morris traversal avoids extra memory usage.

The temporary thread allows the traversal to return to the current node after finishing the left subtree without using stack or recursion. It is removed after use, so the tree remains unchanged.

🔧 Debug

advanced

Identify the Error in Modified Morris Traversal Code

What error will occur when running this modified Morris inorder traversal code snippet?

Code snippet:
let current = root;
while (current !== null) {
if (current.left !== null) {
let pre = current.left;
while (pre.right !== null && pre.right !== current) {
pre = pre.right;
}
if (pre.right === null) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
console.log(current.val);
current = current.right;
}
} else {
console.log(current.val);
current = current.right;
}
}

Note: The condition in the first if is reversed from standard Morris traversal.

A Infinite loop due to missing thread creation when left is null

B Correct output with no errors

C SyntaxError because of missing semicolons

D TypeError because current.left might be undefined

💡 Hint

Check what happens when current.left is null in this code.

The code only creates threads when current.left is not null, but the condition is reversed, so when current.left is null, it skips thread creation and can get stuck in an infinite loop.

📝 Syntax

advanced

Identify Syntax Error in Morris Traversal Implementation

Which option contains a syntax error that prevents the Morris inorder traversal code from running?

A if (pre.right === null) { pre.right = current; current = current.left; } else { pre.right = null; console.log(current.val); current = current.right; }

B while (pre.right !== null && pre.right !== current) pre = pre.right;

C class Node { val: number; left: Node | null; right: Node | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } }

D

let current = root
while (current !== null) { if (current.left === null) { console.log(current.val); current = current.right } else { let pre = current.left; while (pre.right !== null && pre.right !== current) { pre = pre.right } if (pre.right === null) { pre.right = current; current = current.left; } else { pre.right = null; console.log(current.val); current = current.right } } }

💡 Hint

Look for missing semicolons or braces in the code.

Option D is missing semicolons between statements inside the if block, causing syntax errors.

🚀 Application

expert

Number of Temporary Threads Created in Morris Traversal

Given a binary tree with 5 nodes arranged as:
4
/ \
2 5
/ \
1 3

How many temporary threads (links) will Morris inorder traversal create during the full traversal?

A 4

B 2

C 3

D 5

💡 Hint

Count how many nodes have a left child and thus create a thread to their inorder predecessor.

Threads are created for nodes with left children. Nodes 4 and 2 have left children, so threads are created for them. Node 2's left child 1 has no left child, so no thread. Total threads = 2 + 1 (for node 2's left subtree) = 3.