Morris Traversal Inorder Without Stack in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Simple Tree

What is the output of the Morris inorder traversal on the following binary tree?

Tree structure:
2
/ \
1 3

Code snippet uses Morris traversal to print node values in order.

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function morrisInorder(root) {
  let result = [];
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      result.push(current.val);
      current = current.right;
    } else {
      let pre = current.left;
      while (pre.right !== null && pre.right !== current) {
        pre = pre.right;
      }
      if (pre.right === null) {
        pre.right = current;
        current = current.left;
      } else {
        pre.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }
  return result;
}

const root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);
console.log(morrisInorder(root));

A [3, 2, 1]

B [1, 2, 3]

C [1, 3, 2]

D [2, 1, 3]

💡 Hint

Morris traversal prints nodes in inorder sequence without recursion or stack.

Morris traversal visits nodes in inorder: left subtree, root, right subtree. For the tree 2 with left child 1 and right child 3, inorder is 1, 2, 3.

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Left-Skewed Tree

What is the output of the Morris inorder traversal on this left-skewed binary tree?

Tree structure:
4
/
3
/
2
/
1

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function morrisInorder(root) {
  let result = [];
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      result.push(current.val);
      current = current.right;
    } else {
      let pre = current.left;
      while (pre.right !== null && pre.right !== current) {
        pre = pre.right;
      }
      if (pre.right === null) {
        pre.right = current;
        current = current.left;
      } else {
        pre.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }
  return result;
}

const root = new Node(4);
root.left = new Node(3);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
console.log(morrisInorder(root));

A [1, 2, 3, 4]

B [4, 3, 2, 1]

C [1, 3, 2, 4]

D [2, 1, 3, 4]

💡 Hint

Inorder traversal visits leftmost nodes first.

The inorder traversal of a left-skewed tree visits nodes from smallest to largest: 1, 2, 3, 4.

🔧 Debug

advanced

Identify the Error in Morris Traversal Implementation

The following code attempts Morris inorder traversal but produces incorrect output. What is the bug causing this?

Code snippet:

function morrisInorder(root) {
  let result = [];
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      result.push(current.val);
      current = current.left;  // Bug here
    } else {
      let pre = current.left;
      while (pre.right !== null && pre.right !== current) {
        pre = pre.right;
      }
      if (pre.right === null) {
        pre.right = current;
        current = current.left;
      } else {
        pre.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }
  return result;
}

A The code is missing a base case for empty tree

B The inner while loop condition should check 'pre.left' instead of 'pre.right'

C Line 'current = current.left;' should be 'current = current.right;'

D The result array should be initialized inside the while loop

💡 Hint

When left child is null, traversal should move to right child.

When current.left is null, we must move to current.right to continue traversal. Moving to current.left causes infinite loop or wrong output.

🧠 Conceptual

advanced

Why Morris Traversal Uses Threaded Binary Tree Links

Why does Morris inorder traversal temporarily modify the tree by creating links (threads) from the rightmost node of the left subtree back to the current node?

A To avoid using stack or recursion by remembering the path back to the current node

B To permanently change the tree structure for faster future traversals

C To balance the tree dynamically during traversal

D To store node values temporarily for sorting after traversal

💡 Hint

Think about how Morris traversal avoids extra memory usage.

Morris traversal creates temporary links to remember where to return after visiting left subtree, avoiding stack or recursion.

❓ Predict Output

expert

Output of Morris Traversal on Complex Tree

What is the output of the Morris inorder traversal on this binary tree?

Tree structure:
5
/ \
3 7
/ \ \
2 4 8
/
1

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function morrisInorder(root) {
  let result = [];
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      result.push(current.val);
      current = current.right;
    } else {
      let pre = current.left;
      while (pre.right !== null && pre.right !== current) {
        pre = pre.right;
      }
      if (pre.right === null) {
        pre.right = current;
        current = current.left;
      } else {
        pre.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }
  return result;
}

const root = new Node(5);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.right.right = new Node(8);
root.left.left.left = new Node(1);
console.log(morrisInorder(root));

A [1, 3, 2, 4, 5, 7, 8]

B [1, 2, 3, 4, 5, 7, 8, 6]

C [5, 3, 2, 1, 4, 7, 8]

D [1, 2, 3, 4, 5, 7, 8]

💡 Hint

Inorder traversal visits left subtree, root, then right subtree.

The inorder traversal visits nodes in ascending order for this BST: 1, 2, 3, 4, 5, 7, 8.