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.