Morris Traversal Inorder Without Stack in DSA Typescript - Execution Trace

Concept Flow - Morris Traversal Inorder Without Stack

Start at root

↓

Check if current.left is null?

Yes→Visit current node

↓

Move to current.right

↓

Find predecessor in left subtree

↓

Check if predecessor.right is null?

Yes→Make thread: predecessor.right = current

↓

Remove thread: predecessor.right = null

↓

Move current to current.left

↓

Repeat until current is null

This flow shows how Morris Traversal uses temporary threads to traverse the tree inorder without stack or recursion.

Execution Sample

DSA Typescript

function morrisInorder(root) {
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      visit(current);
      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;
        visit(current);
        current = current.right;
      }
    }
  }
}

This code performs inorder traversal of a binary tree without using stack or recursion by creating temporary threads.

Execution Table

Step	Operation	Current Node	Predecessor Node	Thread Created/Removed	Visual State
1	Start at root	1	null	None	1 / \ 2 3
2	current.left != null, find predecessor	1	2	None	1 / \ 2 3
3	predecessor.right == null, create thread	1	2	Thread 2.right -> 1	1 / \ 2->1 3
4	Move current to left child	2	null	None	1 / \ 2->1 3
5	current.left == null, no predecessor needed	2	null	None	1 / \ 2->1 3
6	current.left == null, visit node	2	null	None	Visited: 2 1 / \ 2->1 3
7	Move current to right child	1	2	None	Visited: 2 1 / \ 2->1 3
8	predecessor.right == current, remove thread	1	2	Remove thread 2.right	Visited: 2 1 / \ 2 3
9	Visit current node	1	2	None	Visited: 2,1 1 / \ 2 3
10	Move current to right child	3	null	None	Visited: 2,1 1 / \ 2 3
11	current.left == null, visit node	3	null	None	Visited: 2,1,3 1 / \ 2 3
12	Move current to right child	null	null	None	Visited: 2,1,3
13	current is null, traversal ends	null	null	None	Traversal complete: 2 -> 1 -> 3

💡 current becomes null, traversal ends

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 9	After Step 11	Final
current	1	1	2	2	1	3	null
predecessor	null	2	null	null	2	null	null
thread	None	2.right->1	2.right->1	2.right->1	Removed	None	None
visited_nodes	[]	[]	[]	[2]	[2,1]	[2,1,3]	[2,1,3]

Key Moments - 3 Insights

Why do we create a thread from predecessor.right to current?

Creating the thread (see step 3) allows us to return to the current node after finishing the left subtree without using a stack.

Why do we remove the thread when predecessor.right equals current?

Removing the thread (step 8) restores the original tree structure and signals that the left subtree has been fully visited.

What happens when current.left is null?

When current.left is null (steps 6 and 11), we visit the current node and move to its right child directly.

Visual Quiz - 3 Questions

Look at the execution table, what is the 'current' node at step 6?

A 1

B 2

C 3

D null

💡 Hint

Check the 'Current Node' column in row with Step 6.

At which step is the thread from predecessor.right to current removed?

A Step 8

B Step 11

C Step 3

D Step 13

💡 Hint

Look for 'Remove thread' in the 'Thread Created/Removed' column.

If the tree had no left children, how would the traversal proceed?

A It would create threads for all nodes

B It would get stuck in an infinite loop

C It would visit nodes and move right without creating threads

D It would skip visiting nodes

💡 Hint

Refer to steps where current.left is null and no threads are created.

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Uses temporary threads to traverse left subtree.
- If current.left is null, visit node and move right.
- Else find predecessor, create thread if none.
- Remove thread after left subtree visited.
- No stack or recursion needed.
- Restores tree structure after traversal.

Full Transcript

Morris Traversal Inorder Without Stack uses temporary threads to traverse a binary tree inorder without extra memory. Starting at the root, if the current node has no left child, it is visited and traversal moves to the right child. If there is a left child, the algorithm finds the rightmost node (predecessor) in the left subtree. If the predecessor's right pointer is null, a thread is created to the current node, and traversal moves to the left child. If the thread already exists, it is removed, the current node is visited, and traversal moves to the right child. This process repeats until all nodes are visited and the current pointer becomes null. The tree structure is restored by removing all threads. This method avoids using stack or recursion by temporarily modifying the tree.

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