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.