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

↓

Visit current node

↓

Move to current.right

↓

Repeat until current is null

↓

Done

Traverse the tree without stack by creating temporary threads to predecessors, visiting nodes in inorder.

Execution Sample

DSA Java

TreeNode current = root;
while (current != null) {
  if (current.left == null) {
    visit(current);
    current = current.right;
  } else {
    TreeNode pred = current.left; // find predecessor
    while (pred.right != null && pred.right != current) {
      pred = pred.right;
    }
    if (pred.right == null) {
      pred.right = current; // create thread
      current = current.left;
    } else {
      pred.right = null; // remove thread
      visit(current);
      current = current.right;
    }
  }
}

Traverse binary tree inorder without stack by threading predecessors.

Execution Table

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

💡 current becomes null, traversal complete

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 8	After Step 10	Final
current	1	1	2	2	1	3	null
predecessor	null	2	null	null	2	null	null
thread	None	Created at 2.right	Created at 2.right	Created at 2.right	Removed at 2.right	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 after visiting the current node?

Removing the thread (Step 8) restores the original tree structure and prevents infinite loops during traversal.

What happens when current.left is null?

When current.left is null (Step 6 and 10), we visit the current node directly and move to current.right.

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 3

C Step 8

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 10

B Step 6

C Step 8

D Step 12

💡 Hint

Look at the 'Visited Node' column and find when node 1 appears.

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

A Traversal would visit nodes directly without creating threads

B Traversal would not visit any nodes

C Threads would still be created

D Traversal would get stuck in an infinite loop

💡 Hint

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

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Traverse binary tree inorder without recursion or stack.
- Use temporary threads from predecessor.right to current.
- Visit nodes when left subtree is done or no left child.
- Remove threads to restore tree.
- Efficient O(n) time, O(1) space traversal.

Full Transcript

Morris Traversal is a way to visit all nodes of a binary tree in inorder without using extra space like stack or recursion. It works by creating temporary links called threads from a node's inorder predecessor back to the node itself. We start at the root and for each node, if it has no left child, we visit it and move to its right child. If it has a left child, we find its inorder predecessor in the left subtree. If the predecessor's right pointer is null, we create a thread to the current node and move current to its left child. If the thread already exists, we remove it, visit the current node, and move to its right child. This process continues until all nodes are visited and the tree is restored to its original shape. The traversal runs in linear time and uses constant space.

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 requires the tree to be balanced

B. It is faster than all other traversal methods

C. It only works on binary search trees

D. It uses no extra space for stack or recursion

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal modifies tree links temporarily to avoid using stack or recursion, so it uses O(1) extra space.

2. Step 2: Compare with traditional methods

   Traditional inorder traversal uses recursion or stack which require O(h) space, where h is tree height.

3. Final Answer:

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

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris uses threaded links to avoid stack [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Assuming it only works on BSTs
• Believing it requires balanced trees

2. Which of the following code snippets correctly creates the temporary thread link in Morris Traversal inorder method?

easy

A. current.right = predecessor;

B. current.left = predecessor;

C. predecessor.right = current;

D. predecessor.left = current;

Solution

1. Step 1: Identify the thread link direction

   In Morris Traversal, the right child of the inorder predecessor is linked to current node to create a thread.

2. Step 2: Match with code snippet

   The correct assignment is predecessor.right = current; to create the temporary link.

3. Final Answer:

   predecessor.right = current; -> Option C

4. Quick Check:

   Thread link = predecessor.right = current [OK]

Hint: Thread link always sets predecessor.right to current [OK]

Common Mistakes:

• Assigning current.left to predecessor instead
• Using predecessor.left instead of right
• Confusing current.right with predecessor.right

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

    2
   / \
  1   3

medium

A. [1, 2, 3]

B. [2, 1, 3]

C. [3, 2, 1]

D. [1, 3, 2]

Solution

1. Step 1: Perform inorder traversal manually

   Inorder traversal visits left subtree, root, then right subtree. For this tree: left=1, root=2, right=3.

2. Step 2: List nodes in inorder

   Nodes visited in order: 1, 2, 3.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Inorder = left-root-right = [1, 2, 3] [OK]

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

Common Mistakes:

• Confusing preorder or postorder with inorder
• Mixing up left and right child order
• Assuming Morris changes traversal order

4. Consider this buggy snippet from a Morris inorder traversal implementation:

while (current != null) {
  if (current.left == null) {
    System.out.print(current.val + " ");
    current = current.right;
  } else {
    TreeNode predecessor = current.left;
    while (predecessor.right != null) {
      predecessor = predecessor.right;
    }
    predecessor.right = current;
    current = current.left;
  }
}

What is the main bug causing an infinite loop?

medium

A. Not printing current.val when left is not null

B. Not checking if predecessor.right == current before linking

C. Not moving current to current.right when left is null

D. Not initializing predecessor correctly

Solution

1. Step 1: Identify missing condition in inner loop

   The inner while loop should stop if predecessor.right == current to avoid infinite loop.

2. Step 2: Explain infinite loop cause

   Without checking predecessor.right == current, the loop never breaks and keeps moving right, causing infinite loop.

3. Final Answer:

   Not checking if predecessor.right == current before linking -> Option B

4. Quick Check:

   Check predecessor.right == current to break loop [OK]

Hint: Always check predecessor.right == current to avoid loops [OK]

Common Mistakes:

• Ignoring thread existence check
• Assuming printing happens in else block
• Incorrect predecessor initialization

5. Given a binary tree where some nodes have only left children, how does Morris Traversal handle these nodes to produce the inorder sequence without extra space?

hard

A. It creates temporary right links from the rightmost node of left subtree back to current node

B. It skips nodes with only left children to avoid infinite loops

C. It uses recursion internally to handle left-only nodes

D. It converts the tree into a linked list before traversal

Solution

1. Step 1: Understand Morris Traversal threading

   For nodes with left children, Morris Traversal finds the rightmost node in left subtree and links its right pointer to current node temporarily.

2. Step 2: Explain handling of left-only nodes

   This threading allows traversal to return to current node after left subtree is processed, enabling inorder traversal without stack or recursion.

3. Final Answer:

   It creates temporary right links from the rightmost node of left subtree back to current node -> Option A

4. Quick Check:

   Threading rightmost left subtree node to current [OK]

Hint: Thread rightmost left child back to current node [OK]

Common Mistakes:

• Thinking recursion is used internally
• Assuming nodes are skipped
• Believing tree is converted to linked list