Morris Traversal Inorder Without Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Simple Tree

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

Tree structure:
2
/ \
1 3

Assume the traversal prints node values separated by spaces.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil && pre.Right != current {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

func main() {
    root := &Node{Val: 2}
    root.Left = &Node{Val: 1}
    root.Right = &Node{Val: 3}
    morrisInorder(root)
}

A 1 2 3

B 2 1 3

C 3 2 1

D 1 3 2

💡 Hint

Inorder traversal visits left subtree, then node, then right subtree.

Morris inorder traversal visits nodes in ascending order for a BST. The tree nodes are 1, 2, 3. So output is '1 2 3 '.

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Tree with Only Left Children

What is the output of the Morris inorder traversal on this tree?

Tree structure:
4
/
3
/
2
/
1

Assume the traversal prints node values separated by spaces.

DSA Go

package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil && pre.Right != current {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

func main() {
    root := &Node{Val: 4}
    root.Left = &Node{Val: 3}
    root.Left.Left = &Node{Val: 2}
    root.Left.Left.Left = &Node{Val: 1}
    morrisInorder(root)
}

A 1 3 2 4

B 1 2 3 4

C 4 3 2 1

D 2 1 3 4

💡 Hint

Inorder traversal visits nodes from smallest to largest in this left-skewed tree.

The inorder traversal visits nodes from leftmost (1) up to root (4) in ascending order.

🔧 Debug

advanced

Identify the Bug in Morris Traversal Code

The following Go code attempts Morris inorder traversal but produces incorrect output. What is the bug?

DSA Go

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

A The inner loop misses checking if pre.Right == current, causing infinite loop or wrong threading.

B The code should print current.Val before setting pre.Right = current.

C The code incorrectly sets pre.Left instead of pre.Right.

D The code should move current to current.Right before printing current.Val.

💡 Hint

Check the condition inside the inner while loop that finds the predecessor.

The inner loop must check pre.Right != nil AND pre.Right != current to avoid infinite loops and correctly restore tree structure.

🧠 Conceptual

advanced

Why Morris Traversal Uses Threaded Links

Why does Morris inorder traversal create temporary links (threads) from the inorder predecessor to the current node?

A To permanently modify the tree structure for faster future traversals.

B To store node values temporarily during traversal.

C To avoid using a stack or recursion by remembering where to return after visiting left subtree.

D To balance the tree dynamically during traversal.

💡 Hint

Think about how recursion or stack remembers the path back to a node.

Morris traversal uses threads to remember the return path without extra memory, enabling O(1) space traversal.

🚀 Application

expert

Count Nodes Using Morris Traversal Without Extra Space

Using Morris inorder traversal, how can you count the total number of nodes in a binary tree without using recursion or a stack?

A Count nodes by traversing only right children and ignoring left children.

B Count nodes by incrementing counter only when creating a thread link.

C Count nodes by incrementing counter only when removing a thread link.

D Traverse the tree with Morris inorder and increment a counter each time a node is visited (printed).

💡 Hint

Each node is visited exactly once in inorder traversal.

In Morris traversal, each node is printed exactly once when visited. Counting these visits gives total nodes.

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

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 the tree temporarily to avoid using stack or recursion, so it uses O(1) extra space.

2. Step 2: Compare with other methods

   Traditional inorder traversal uses recursion or stack which requires 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:

   Morris Traversal = O(1) space [OK]

Hint: Morris Traversal saves space by threading nodes [OK]

Common Mistakes:

• Thinking it is faster than all methods
• Assuming it only works on BSTs
• Believing it needs balanced trees

2. Which of the following Go code snippets correctly initializes a pointer to the current node for Morris inorder traversal?

easy

A. current := root

B. var current *Node = nil

C. current := &root

D. current := root.left

Solution

1. Step 1: Understand pointer initialization

   For traversal, current should start at root node, so current := root is correct.

2. Step 2: Check other options

   var current *Node = nil sets current to nil, which stops traversal immediately. current := &root takes address of root pointer, incorrect. current := root.left starts at left child, skipping root.

3. Final Answer:

   current := root -> Option A

4. Quick Check:

   Start traversal at root = current := root [OK]

Hint: Start traversal pointer at root node [OK]

Common Mistakes:

• Initializing current as nil
• Taking address of root pointer
• Starting at root.left instead of root

3. Given the following binary tree and Morris inorder traversal code, what is the printed output?

    2
   / \
  1   3

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil && pre.Right != current {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

medium

A. 2 1 3

B. 1 2 3

C. 3 2 1

D. 1 3 2

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, root, then right subtree. For tree 2 with left 1 and right 3, order is 1 2 3.

2. Step 2: Trace Morris traversal output

   Morris traversal prints nodes in inorder without stack. The code prints 1, then 2, then 3 with spaces.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Inorder of given tree = 1 2 3 [OK]

Hint: Inorder prints left-root-right sequence [OK]

Common Mistakes:

• Confusing preorder or postorder output
• Misreading the tree structure
• Ignoring Morris threading logic

4. Consider this snippet of Morris inorder traversal in Go. What is the bug that causes an infinite loop?

current := root
for current != nil {
    if current.Left != nil {
        pre := current.Left
        for pre.Right != nil {
            pre = pre.Right
        }
        pre.Right = current
        current = current.Left
    } else {
        fmt.Print(current.Val, " ")
        current = current.Right
    }
}

medium

A. Printing node values before traversal

B. Incorrect initialization of current pointer

C. Missing check if pre.Right == current before setting pre.Right = current

D. Not updating current to current.Left in else block

Solution

1. Step 1: Analyze inner loop for threading

   The inner loop finds rightmost node of left subtree. Without checking if pre.Right == current, it keeps looping infinitely.

2. Step 2: Identify missing condition causing infinite loop

   Correct Morris traversal checks if pre.Right is nil or points to current to avoid infinite loop. Missing this causes infinite loop.

3. Final Answer:

   Missing check if pre.Right == current before setting pre.Right = current -> Option C

4. Quick Check:

   Check pre.Right == current to avoid loops [OK]

Hint: Always check if thread already exists before linking [OK]

Common Mistakes:

• Skipping pre.Right == current check
• Wrong pointer updates
• Printing too early

5. You want to modify Morris inorder traversal to count the number of nodes in a binary tree without using extra space or recursion. Which change correctly achieves this?

hard

A. Add a counter variable and increment it each time you print a node's value during traversal

B. Increment counter only when creating a thread (pre.Right = current)

C. Increment counter only when removing a thread (pre.Right = nil)

D. Increment counter only when current.Left is nil

Solution

1. Step 1: Identify when nodes are visited in Morris traversal

   Nodes are printed exactly once: when current.Left == nil or when removing the thread (pre.Right != nil).

2. Step 2: Choose correct increment point for counting

   Incrementing the counter each time a node's value is printed ensures every node is counted exactly once.

3. Final Answer:

   Add a counter variable and increment it each time you print a node's value during traversal -> Option A

4. Quick Check:

   Increment on every print operation [OK]

Hint: Count nodes when printing each node [OK]

Common Mistakes:

• Incrementing only when current.Left is nil (misses nodes with left subtrees)
• Incrementing when creating threads (counts only non-leaf nodes)
• Incrementing when removing threads (counts only non-leaf nodes)