Morris Traversal Inorder Without Stack in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Morris Traversal for inorder tree traversal?

Morris Traversal uses threaded binary trees by temporarily modifying the tree's right pointers to avoid using a stack or recursion, enabling inorder traversal with O(1) extra space.

intermediate

In Morris Traversal, what do we do when the current node has a left child?

We find the rightmost node in the left subtree (predecessor). If its right pointer is null, we set it to point to the current node (threading). If it already points to the current node, we remove the thread and move to the right child.

beginner

Why does Morris Traversal not require a stack or recursion?

Because it temporarily changes the tree structure by creating threads to the inorder successor, allowing traversal without extra memory for stack or recursion.

intermediate

What is the time complexity of Morris Traversal Inorder?

The time complexity is O(n) because each edge is visited at most twice: once to create a thread and once to remove it.

beginner

What happens if the current node has no left child in Morris Traversal?

We print the current node's value and move to its right child directly.

What does Morris Traversal use to avoid stack or recursion?

A Temporary threads in the tree

B Extra stack memory

C Recursion

D Queue data structure

Morris Traversal creates temporary threads (right pointers) to the inorder successor to avoid using stack or recursion.

When finding the predecessor in Morris Traversal, what is the predecessor?

A Leftmost node in the right subtree

B Root node

C Parent node

D Rightmost node in the left subtree

The predecessor is the rightmost node in the current node's left subtree.

What do we do if the predecessor's right pointer is already pointing to the current node?

A Remove the thread and move to right child

B Create a new thread

C Stop traversal

D Move to left child

If the thread exists, we remove it and then move to the right child.

What is the space complexity of Morris Traversal?

A O(log n)

B O(n)

C O(1)

D O(n log n)

Morris Traversal uses O(1) extra space by modifying the tree temporarily.

If a node has no left child, what is the next step in Morris Traversal?

A Move to left child

B Print the node and move to right child

C Create a thread

D Find predecessor

If no left child, print the node and move directly to its right child.

Explain step-by-step how Morris Traversal performs inorder traversal without using a stack or recursion.

Think about how the tree's right pointers are temporarily changed to remember where to go next.

Describe the advantages and potential drawbacks of using Morris Traversal for inorder traversal.

Consider memory usage and tree modification.

Practice

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

easy

A. It is faster than all other traversal methods.

B. It uses no extra space for stack or recursion.

C. It only works for binary search trees.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand space usage in tree traversals

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

2. Step 2: Morris Traversal space optimization

   Morris Traversal cleverly uses threaded binary trees to avoid stack or recursion, thus using O(1) extra space.

3. Final Answer:

   It uses no extra space for stack or recursion. -> Option B

4. Quick Check:

   Morris Traversal = O(1) space [OK]

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

Common Mistakes:

• Thinking Morris is faster in time complexity
• Believing Morris only works on BSTs
• Assuming Morris modifies tree permanently

2. Which of the following TypeScript code snippets correctly initializes the current node for Morris inorder traversal?

easy

A. let current: TreeNode | null = root;

B. let current = null;

C. let current: TreeNode = null;

D. let current: TreeNode = root.left;

Solution

1. Step 1: Identify correct initialization type

   We start traversal from the root node, so current should be root and allow null for empty trees.

2. Step 2: Check TypeScript syntax

   TypeScript requires correct type with possible null, so 'TreeNode | null' is correct.

3. Final Answer:

   let current: TreeNode | null = root; -> Option A

4. Quick Check:

   Correct type and initialization = let current: TreeNode | null = root; [OK]

Hint: Start traversal at root with nullable node type [OK]

Common Mistakes:

• Assigning null without type union
• Starting from root.left instead of root
• Using uninitialized or wrong type

3. Consider the following TypeScript code for Morris inorder traversal on this tree:

    2
   / \
  1   3

What will be the printed output sequence?

medium

A. [3, 2, 1]

B. [2, 1, 3]

C. [1, 2, 3]

D. [1, 3, 2]

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then node, then right subtree. For this tree, order is 1, 2, 3.

2. Step 2: Morris traversal mimics inorder without stack

   Morris traversal outputs nodes in inorder sequence, so output will be [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Inorder of given tree = [1, 2, 3] [OK]

Hint: Inorder = left, root, right sequence [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Assuming Morris changes output order
• Mixing left and right subtree order

4. In this TypeScript snippet for Morris traversal, what is the bug?

while (current !== null) {
  if (current.left === null) {
    console.log(current.val);
    current = current.right;
  } else {
    let predecessor = current.left;
    while (predecessor.right !== null && predecessor.right !== current) {
      predecessor = predecessor.right;
    }
    if (predecessor.right === null) {
      predecessor.right = current;
      current = current.left;
    } else {
      predecessor.right = null;
      // Missing console.log here
      current = current.right;
    }
  }
}

medium

A. Incorrect initialization of predecessor variable.

B. Using '===' instead of '==' in while condition.

C. Not updating current to current.left in else block.

D. Missing printing current.val before moving right after restoring link.

Solution

1. Step 1: Identify missing output in else block

   When restoring the tree link, the node's value must be printed before moving right, else node is skipped.

2. Step 2: Effect of missing print

   Without printing current.val in the unthreading step, nodes with left subtrees are skipped in the output, causing incomplete traversal results.

3. Final Answer:

   Missing printing current.val before moving right after restoring link. -> Option D

4. Quick Check:

   Missing console.log(current.val) in unthreading step causes skipped nodes [OK]

Hint: Print node value when restoring threaded link [OK]

Common Mistakes:

• Ignoring print statement placement
• Confusing predecessor initialization
• Thinking '===' causes infinite loop

5. Given a binary tree with nodes:

      4
     / \
    2   5
   / \
  1   3

Using Morris inorder traversal, what is the exact sequence of node values printed, and why does this method not use extra memory?

hard

A. [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion.

B. [4, 2, 1, 3, 5]; uses recursion internally.

C. [1, 3, 2, 4, 5]; uses a stack to track nodes.

D. [5, 4, 3, 2, 1]; modifies tree permanently.

Solution

1. Step 1: Determine inorder traversal sequence

   Inorder visits left subtree, node, right subtree. For this tree, sequence is 1, 2, 3, 4, 5.

2. Step 2: Explain Morris traversal memory usage

   Morris traversal creates temporary threaded links to predecessor nodes, avoiding stack or recursion, thus using O(1) extra space.

3. Final Answer:

   [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion. -> Option A

4. Quick Check:

   Inorder = [1,2,3,4,5], O(1) space by threading [OK]

Hint: Inorder sequence + threaded links = no extra memory [OK]

Common Mistakes:

• Mixing traversal order
• Assuming recursion or stack used
• Believing tree is permanently changed