Morris Traversal Inorder Without Stack in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start Morris traversal by setting current to root.

DSA Javascript

let current = [1];

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

Aroot

Bnull

Chead

Dthis

Attempts:

3 left

💡 Hint

Common Mistakes

Setting current to null or head instead of root.

We start Morris traversal from the root node, so current should be set to root.

2fill in blank

medium

Complete the condition to check if current has a left child.

DSA Javascript

while (current !== null) {
  if (current.[1] === null) {
    // Process current node
  }
}

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

Aright

Bchild

Cleft

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Checking current.right instead of current.left.

We check if current.left is null to decide if we can process current or need to find predecessor.

3fill in blank

hard

Fix the error in finding the inorder predecessor by completing the loop condition.

DSA Javascript

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

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

Achild

Bleft

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using predecessor.left instead of predecessor.right.

The inorder predecessor is found by moving to the rightmost node in the left subtree, so we check predecessor.right.

4fill in blank

hard

Fill both blanks to create or remove the temporary thread in Morris traversal.

DSA Javascript

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

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

Aright

Bleft

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using left or parent instead of right for the thread pointer.

We create a temporary thread by setting predecessor.right to current, so both blanks are 'right'.

5fill in blank

hard

Fill all three blanks to correctly remove the temporary thread and move current in Morris traversal.

DSA Javascript

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

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

Aright

Bvalue

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Removing thread from left pointer or printing current.left.

We remove the thread by setting predecessor.right to null, print current.value, and move current to current.right.