Morris Traversal Inorder Without Stack in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to move to the left child in Morris Traversal.

DSA Typescript

while (current !== null) {
  if (current.left === null) {
    console.log(current.data);
    current = current[1];
  } else {
    // Find the inorder predecessor
  }
}

Drag options to blanks, or click blank then click option'

A.left

B.parent

C.right

D.next

Attempts:

3 left

💡 Hint

Common Mistakes

Moving to left child instead of right child when left is null.

Trying to access a non-existent parent property.

In Morris Traversal, when the left child is null, we print the current node and move to its right child.

2fill in blank

medium

Complete the code to find the inorder predecessor of the current node.

DSA Typescript

let predecessor = current.left;
while (predecessor.right !== null && predecessor.right !== current) {
  predecessor = predecessor[1];
}

Drag options to blanks, or click blank then click option'

A.next

B.right

C.parent

D.left

Attempts:

3 left

💡 Hint

Common Mistakes

Moving to left child instead of right child when searching for predecessor.

Not checking if predecessor.right equals current to avoid infinite loop.

The inorder predecessor is the rightmost node in the left subtree, so we move to predecessor.right repeatedly.

3fill in blank

hard

Fix the error in the code that creates a temporary link to the current node.

DSA Typescript

if (predecessor.right === null) {
  predecessor[1] = current;
  current = current.left;
}

Drag options to blanks, or click blank then click option'

A.next

B.left

C.parent

D.right

Attempts:

3 left

💡 Hint

Common Mistakes

Setting predecessor.left instead of predecessor.right.

Assigning current.left instead of current.

We create a temporary link from predecessor.right to current to remember the path back.

4fill in blank

hard

Fill both blanks to remove the temporary link and move to the right child.

DSA Typescript

else {
  predecessor[1] = null;
  console.log(current.data);
  current = current[2];
}

Drag options to blanks, or click blank then click option'

A.right

B.left

C.parent

D.next

Attempts:

3 left

💡 Hint

Common Mistakes

Removing predecessor.left instead of predecessor.right.

Moving to current.left instead of current.right after removing link.

We remove the temporary link by setting predecessor.right to null and then move to current.right.

5fill in blank

hard

Fill all three blanks to complete the Morris Traversal loop.

DSA Typescript

while (current !== null) {
  if (current.left === null) {
    console.log(current.data);
    current = current[1];
  } else {
    let predecessor = current.left;
    while (predecessor.right !== null && predecessor.right !== current) {
      predecessor = predecessor[2];
    }
    if (predecessor.right === null) {
      predecessor[3] = current;
      current = current.left;
    } else {
      predecessor.right = null;
      console.log(current.data);
      current = current.right;
    }
  }
}

Drag options to blanks, or click blank then click option'

A.right

B.left

C.parent

D.next

Attempts:

3 left

💡 Hint

Common Mistakes

Using .left instead of .right in any of the blanks.

Setting predecessor.left instead of predecessor.right for the temporary link.

The traversal moves to current.right when left is null, finds predecessor by moving to predecessor.right, and creates a temporary link predecessor.right = current.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to the traditional recursive or stack-based methods?

easy

A. It is faster than all other traversal methods.

B. It uses no extra space for stack or recursion.

C. It only works for binary search trees.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand space usage in tree traversals

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

2. Step 2: Morris Traversal space optimization

   Morris Traversal cleverly uses threaded binary trees to avoid stack or recursion, thus using O(1) extra space.

3. Final Answer:

   It uses no extra space for stack or recursion. -> Option B

4. Quick Check:

   Morris Traversal = O(1) space [OK]

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

Common Mistakes:

• Thinking Morris is faster in time complexity
• Believing Morris only works on BSTs
• Assuming Morris modifies tree permanently

2. Which of the following TypeScript code snippets correctly initializes the current node for Morris inorder traversal?

easy

A. let current: TreeNode | null = root;

B. let current = null;

C. let current: TreeNode = null;

D. let current: TreeNode = root.left;

Solution

1. Step 1: Identify correct initialization type

   We start traversal from the root node, so current should be root and allow null for empty trees.

2. Step 2: Check TypeScript syntax

   TypeScript requires correct type with possible null, so 'TreeNode | null' is correct.

3. Final Answer:

   let current: TreeNode | null = root; -> Option A

4. Quick Check:

   Correct type and initialization = let current: TreeNode | null = root; [OK]

Hint: Start traversal at root with nullable node type [OK]

Common Mistakes:

• Assigning null without type union
• Starting from root.left instead of root
• Using uninitialized or wrong type

3. Consider the following TypeScript code for Morris inorder traversal on this tree:

    2
   / \
  1   3

What will be the printed output sequence?

medium

A. [3, 2, 1]

B. [2, 1, 3]

C. [1, 2, 3]

D. [1, 3, 2]

Solution

1. Step 1: Understand inorder traversal order

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

2. Step 2: Morris traversal mimics inorder without stack

   Morris traversal outputs nodes in inorder sequence, so output will be [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Inorder of given tree = [1, 2, 3] [OK]

Hint: Inorder = left, root, right sequence [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Assuming Morris changes output order
• Mixing left and right subtree order

4. In this TypeScript snippet for Morris traversal, what is the bug?

while (current !== null) {
  if (current.left === null) {
    console.log(current.val);
    current = current.right;
  } else {
    let 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;
      // Missing console.log here
      current = current.right;
    }
  }
}

medium

A. Incorrect initialization of predecessor variable.

B. Using '===' instead of '==' in while condition.

C. Not updating current to current.left in else block.

D. Missing printing current.val before moving right after restoring link.

Solution

1. Step 1: Identify missing output in else block

   When restoring the tree link, the node's value must be printed before moving right, else node is skipped.

2. Step 2: Effect of missing print

   Without printing current.val in the unthreading step, nodes with left subtrees are skipped in the output, causing incomplete traversal results.

3. Final Answer:

   Missing printing current.val before moving right after restoring link. -> Option D

4. Quick Check:

   Missing console.log(current.val) in unthreading step causes skipped nodes [OK]

Hint: Print node value when restoring threaded link [OK]

Common Mistakes:

• Ignoring print statement placement
• Confusing predecessor initialization
• Thinking '===' causes infinite loop

5. Given a binary tree with nodes:

      4
     / \
    2   5
   / \
  1   3

Using Morris inorder traversal, what is the exact sequence of node values printed, and why does this method not use extra memory?

hard

A. [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion.

B. [4, 2, 1, 3, 5]; uses recursion internally.

C. [1, 3, 2, 4, 5]; uses a stack to track nodes.

D. [5, 4, 3, 2, 1]; modifies tree permanently.

Solution

1. Step 1: Determine inorder traversal sequence

   Inorder visits left subtree, node, right subtree. For this tree, sequence is 1, 2, 3, 4, 5.

2. Step 2: Explain Morris traversal memory usage

   Morris traversal creates temporary threaded links to predecessor nodes, avoiding stack or recursion, thus using O(1) extra space.

3. Final Answer:

   [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion. -> Option A

4. Quick Check:

   Inorder = [1,2,3,4,5], O(1) space by threading [OK]

Hint: Inorder sequence + threaded links = no extra memory [OK]

Common Mistakes:

• Mixing traversal order
• Assuming recursion or stack used
• Believing tree is permanently changed