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.

Practice

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

easy

A. It sorts the tree nodes during traversal

B. It is faster because it uses multiple threads

C. It requires the tree to be a binary search tree

D. It uses no extra space for stack or recursion, only modifies tree temporarily

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal does not use recursion or an explicit stack, instead it temporarily modifies the tree's right pointers to traverse.

2. Step 2: Compare with traditional methods

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

3. Final Answer:

   It uses no extra space for stack or recursion, only modifies tree temporarily -> Option D

4. Quick Check:

   Space efficiency = No extra stack [OK]

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

Common Mistakes:

• Thinking Morris sorts nodes
• Assuming it needs a binary search tree
• Believing it uses threads or parallelism

2. Which of the following code snippets correctly initializes the current pointer for Morris inorder traversal in C++?

easy

A. Node current = root;

B. Node* current = root;

C. Node* current = new Node(root);

D. Node current = *root;

Solution

1. Step 1: Understand pointer usage in C++ for tree traversal

   We need a pointer to traverse nodes, so current should be a pointer to Node initialized to root pointer.

2. Step 2: Analyze options

   Node* current = root; correctly declares a pointer and assigns root. Options B and D declare objects, not pointers. Node* current = new Node(root); incorrectly uses new with root pointer.

3. Final Answer:

   Node* current = root; -> Option B

4. Quick Check:

   Pointer initialization = Node* current = root [OK]

Hint: Use pointer Node* current = root for traversal [OK]

Common Mistakes:

• Declaring current as object instead of pointer
• Using new operator incorrectly
• Dereferencing root without pointer

3. Consider the following C++ code snippet implementing Morris inorder traversal on a binary tree with nodes 1, 2, 3 where 1 is root, 2 is left child, and 3 is right child. What is the output printed?

struct Node {
  int data;
  Node* left;
  Node* right;
};

void morrisInorder(Node* root) {
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      std::cout << current->data << " ";
      current = current->right;
    } else {
      Node* pre = current->left;
      while (pre->right != nullptr && pre->right != current) {
        pre = pre->right;
      }
      if (pre->right == nullptr) {
        pre->right = current;
        current = current->left;
      } else {
        pre->right = nullptr;
        std::cout << current->data << " ";
        current = current->right;
      }
    }
  }
}

// Tree: 1
//      / \
//     2   3

int main() {
  Node n1{1, nullptr, nullptr};
  Node n2{2, nullptr, nullptr};
  Node n3{3, nullptr, nullptr};
  n1.left = &n2;
  n1.right = &n3;
  morrisInorder(&n1);
  return 0;
}

medium

A. 3 1 2

B. 1 2 3

C. 2 1 3

D. 2 3 1

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then root, then right subtree. For tree 1 with left 2 and right 3, order is 2, 1, 3.

2. Step 2: Trace Morris traversal output

   Morris traversal prints nodes in inorder without stack. It prints 2 first (left child), then 1 (root), then 3 (right child).

3. Final Answer:

   2 1 3 -> Option C

4. Quick Check:

   Inorder output = 2 1 3 [OK]

Hint: Inorder = left, root, right; output matches 2 1 3 [OK]

Common Mistakes:

• Confusing preorder or postorder output
• Ignoring temporary link restoration
• Assuming output is sorted only for BST

4. The following code attempts Morris inorder traversal but causes an infinite loop. What is the bug?

void morrisInorder(Node* root) {
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      std::cout << current->data << " ";
      current = current->right;
    } else {
      Node* pre = current->left;
      while (pre->right != nullptr) {
        pre = pre->right;
      }
      if (pre->right == nullptr) {
        pre->right = current;
        current = current->left;
      } else {
        pre->right = nullptr;
        std::cout << current->data << " ";
        current = current->right;
      }
    }
  }
}

medium

A. The inner while loop misses checking pre->right != current causing infinite loop

B. The current pointer is not updated after printing

C. The code does not handle nullptr root

D. The pre pointer is not initialized correctly

Solution

1. Step 1: Analyze inner while loop condition

   The inner while loop should check if pre->right is not nullptr and not equal to current to avoid infinite loop.

2. Step 2: Identify missing condition causing infinite loop

   Missing check pre->right != current causes loop to never break when pre->right points back to current, causing infinite loop.

3. Final Answer:

   The inner while loop misses checking pre->right != current causing infinite loop -> Option A

4. Quick Check:

   Loop condition must check pre->right != current [OK]

Hint: Check inner loop condition includes pre->right != current [OK]

Common Mistakes:

• Ignoring second condition in inner loop
• Forgetting to update current after printing
• Not handling empty tree

5. You want to modify Morris inorder traversal to count the number of nodes in a binary tree without using extra space or recursion. Which modification is correct?

void morrisCount(Node* root) {
  int count = 0;
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      count++;
      current = current->right;
    } else {
      Node* pre = current->left;
      while (pre->right != nullptr && pre->right != current) {
        pre = pre->right;
      }
      if (pre->right == nullptr) {
        pre->right = current;
        current = current->left;
      } else {
        pre->right = nullptr;
        count++;
        current = current->right;
      }
    }
  }
  std::cout << count << std::endl;
}

hard

A. This code correctly counts nodes using Morris traversal without extra space

B. Counting should be done only when pre->right is nullptr

C. Count variable must be global to work correctly

D. Morris traversal cannot be used to count nodes without recursion

Solution

1. Step 1: Understand counting during Morris traversal

   Count nodes when visiting them: when left is nullptr or after restoring links (pre->right == current).

2. Step 2: Verify code increments count correctly

   Code increments count in both cases correctly, so it counts all nodes without extra space or recursion.

3. Final Answer:

   This code correctly counts nodes using Morris traversal without extra space -> Option A

4. Quick Check:

   Count increments on node visit = correct [OK]

Hint: Increment count on node visit before moving right [OK]

Common Mistakes:

• Counting only once per node visit
• Making count global unnecessarily
• Assuming Morris can't count nodes