Morris Traversal Inorder Without Stack in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to move to the left child of the current node.

DSA C++

current = current->[1];

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

Aright

Bparent

Cnext

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'right' instead of 'left' to move to the left child.

The Morris traversal moves to the left child to find the inorder predecessor.

2fill in blank

medium

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

DSA C++

predecessor = current->left;
while (predecessor->[1] != nullptr && predecessor->[1] != current) {
    predecessor = predecessor->[1];
}

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

Aleft

Bright

Cparent

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Moving left instead of right when searching for the predecessor.

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

3fill in blank

hard

Fix the error in the condition to check if the predecessor's right pointer is null.

DSA C++

if (predecessor->[1] == nullptr) {
    predecessor->right = current;
    current = current->left;
}

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

Aright

Bleft

Cparent

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Checking predecessor->left instead of predecessor->right.

The Morris traversal uses the right pointer of the predecessor to create a temporary link to the current node.

4fill in blank

hard

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

DSA C++

else {
    predecessor->[1] = nullptr;
    [2];
}

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

Aright

Bcurrent = current->right

Ccurrent = current->left

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Setting predecessor->left to nullptr or moving to current->left instead of current->right.

We remove the temporary link by setting predecessor->right to nullptr and then move to the right subtree.

5fill in blank

hard

Fill all three blanks to print the current node's data and move to the right child.

DSA C++

std::cout << current->[1] << " ";
current = current->[2];
// Loop continues until current is [3]

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

Adata

Bleft

Cnullptr

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Printing left or right pointer instead of data, moving left instead of right, or wrong loop end condition.

Print the data of the current node, move to the right child, and continue until current is nullptr.