Morris Traversal Inorder Without Stack in DSA Javascript - 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

No↓

Find predecessor in left subtree

↓

Check if predecessor.right is null?

Yes→Make thread: predecessor.right = current, move current to current.left

No↓

Remove thread: predecessor.right = null, visit current, move current to current.right

↓

Repeat until current is null

↓

Traversal complete

The traversal moves through the tree without stack by creating temporary threads to predecessors, visiting nodes in inorder sequence.

Execution Sample

DSA Javascript

function morrisInorder(root) {
  let current = root;
  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;
        console.log(current.val);
        current = current.right;
      }
    }
  }
}

This code prints the inorder traversal of a binary tree using Morris Traversal without using stack or recursion.

Execution Table

Step	Operation	Current Node	Predecessor	Thread Created/Removed	Visited Node	Visual Tree State
1	Start at root	1	N/A	No	No	1 / \ 2 3
2	current.left != null, find predecessor	1	2	No	No	1 / \ 2 3
3	predecessor.right == null, create thread	1	2	Thread created: 2.right = 1	No	1 / \ 2→ 3
4	Move current to left child	2	N/A	No	No	1 / \ 2→ 3
5	current.left == null, visit node	2	N/A	No	Visited 2	1 / \ 2→ 3
6	Move current to right child	1	N/A	No	No	1 / \ 2→ 3
7	current.left != null, find predecessor	1	2	No	No	1 / \ 2→ 3
8	predecessor.right == current, remove thread	1	2	Thread removed: 2.right = null	No	1 / \ 2 3
9	Visit current node	1	N/A	No	Visited 1	1 / \ 2 3
10	Move current to right child	3	N/A	No	No	1 / \ 2 3
11	current.left == null, visit node	3	N/A	No	Visited 3	1 / \ 2 3
12	Move current to right child	null	N/A	No	No	1 / \ 2 3
13	current is null, traversal ends	null	N/A	No	No	1 / \ 2 3

💡 Traversal ends when current becomes null after visiting all nodes.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 8	After Step 9	After Step 11	Final
current	1	1	2	1	1	3	null
predecessor	N/A	2	N/A	2	N/A	N/A	N/A
thread	No	Yes (2.right=1)	Yes (2.right=1)	No (2.right=null)	No	No	No

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 later?

Removing the thread (see Step 8) restores the original tree structure after visiting the current node.

Why do we visit nodes only when current.left is null or after removing a thread?

Visiting nodes at these points (Steps 5, 9, 11) ensures inorder sequence: left subtree, node, then right subtree.

Visual Quiz - 3 Questions

Look at the execution table, at which step is the thread from node 2 to node 1 created?

A Step 5

B Step 8

C Step 3

D Step 10

💡 Hint

Check the 'Thread Created/Removed' column in the execution table.

At which step does the traversal visit node 1?

A Step 5

B Step 9

C Step 8

D Step 11

💡 Hint

Look at the 'Visited Node' column in the execution table.

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

A It would visit nodes immediately and move to right child.

B It would create threads for every node.

C It would get stuck in an infinite loop.

D It would skip visiting nodes.

💡 Hint

Refer to the condition when current.left is null in the code and execution table.

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Uses threaded binary tree concept.
- Creates temporary right links (threads) to predecessors.
- Visits nodes when left subtree is done.
- Removes threads to restore tree.
- Traverses in O(n) time and O(1) space.

Full Transcript

Morris Traversal is a way to do inorder traversal of a binary tree without using extra space like stack or recursion. It works by creating temporary threads from a node's inorder predecessor back to the node. This allows the traversal to return to the node after finishing its left subtree. When the thread is encountered again, it is removed and the node is visited. If a node has no left child, it is visited immediately and traversal moves to the right child. This process continues until all nodes are visited and the tree is restored to its original shape. The execution table shows each step including thread creation, removal, and node visits. The variable tracker shows how current and predecessor pointers move and how threads are created and removed. Key moments clarify why threads are needed and when nodes are visited. The visual quiz tests understanding of these steps. This method achieves inorder traversal in linear time with constant space.